BFS Approach | Python | TC: O(n^2) | SC: O(n)
Complexity\n- Time complexity:O(n^2)\n\n- Space complexity:O(n)\n\n# Code\n\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n
# Complexity\n- Time complexity:O(n^2)\n\n- Space complexity:O(n)\n\n# Code\n```\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        res = [0]*(n+1)\n        graph = defaultdict(list)\n        \n        for i in range(1,n):\n            graph[i].append(i+1)\n            graph[i+1].append(i)\n            \n        graph[x].append(y)\n        graph[y].append(x)\n        \n        def bfs(node):\n            q = deque([(0,node)])\n            visited = {}\n            \n            while q:\n                d,curr = q.popleft()\n                if len(visited)==n:\n                    break\n                \n                visited[curr]=d\n\n                for nei in graph[curr]:\n                    if nei not in visited:\n                        visited[nei]=d+1\n                        q.append((d+1,nei))\n                        \n            return visited\n                        \n        for i in range(1,n+1):\n            distMap = bfs(i)\n            for val in distMap.values():\n                res[val]+=1\n            \n        return res[1:]\n            \n```
['Breadth-First Search', 'Graph', 'Queue', 'Python3']