Node Reachability by Path Length
Given an undirected graph with N nodes and M edges, and a starting node S, find the number of nodes that are exactly K edges away from S for each K from 0 up to N-1. You should output these counts in order for K=0, K=1, ..., K=N-1.
Input
The first line contains two integers N and M, the number of nodes and edges. Nodes are numbered 1 to N. The second line contains the starting node S. The next M lines each contain two integers u and v, representing an undirected edge between node u and node v.
Output
Print N integers, where the i-th integer (0-indexed) is the count of nodes exactly i edges away from S.
Constraints
1 <= N <= 200000 0 <= M <= 200000 1 <= S <= N
Example 1
5 4 1 1 2 1 3 2 4 3 5
1 2 2 0 0
Starting at node 1. Node 1 is 0 edges away. Nodes 2 and 3 are 1 edge away. Nodes 4 and 5 are 2 edges away. Counts: [1, 2, 2, 0, 0]
Example 2
7 5 4 1 2 2 3 3 4 4 5 5 6
1 2 2 1 0 0 0
Starting at node 4. Node 4 is 0 edges away. Nodes 3, 5 are 1 edge away. Nodes 2, 6 are 2 edges away. Node 1 is 3 edges away. Node 7 is unreachable. Counts: [1, 2, 2, 1, 0, 0, 0]
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 4 1 1 2 1 3 2 4 3 5
7 5 4 1 2 2 3 3 4 4 5 5 6