Most simple multi-source BFS
Intuition\nBFS gives us min dist to each house2 from house1. We want to start BFS from each house to get all pairs, so we use multi-source BFS\n\n# Approach\nBF
# Intuition\nBFS gives us min dist to each `house2` from `house1`. We want to start BFS from each house to get all pairs, so we use multi-source BFS\n\n# Approach\nBFS from each house keeping track of `dist` between nodes and building `res`. Need `visited`set to prevent cycle.\n\n# Code\n```\nclass Solution:\n    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:\n        graph = dict()\n        for i in range(1, n):\n            graph[i] = graph.get(i, []) + [i+1]\n            graph[i+1] = graph.get(i+1, []) + [i]\n        graph[x] += [y]\n        graph[y] += [x]\n    \n        res = [0] * n\n        q = deque()\n        for i in range(1, n+1):\n            q.append((i, 0, set()))  # (house, dist, visited)\n        while q:\n            house, dist, visited = q.popleft()\n            if house not in visited:\n                visited.add(house)\n                if dist > 0:\n                    res[dist-1] += 1\n                for nei in graph[house]:\n                    q.append((nei, dist+1, visited))\n        return res\n\n```
['Breadth-First Search', 'Graph', 'Python3']