Shortest Path in an Unweighted Graph

Shortest Path in an Unweighted Graph

Find the shortest path from a source to all nodes in an unweighted graph using BFS.

Input format

The first line contains N, M, and SRC. The next M lines contain undirected edge pairs.

Output format

Print N distances from SRC; -1 if unreachable.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

14 7 0
3 13
5 12
1 2
7 13
0 10
9 12
8 10

0 -1 -1 -1 -1 -1 -1 -1 2 -1 1 -1 -1 -1

27 39 7
7 14
9 25
6 22
3 10
19 20
8 15
18 23
20 24
1 16
5 24
6 21
3 4
6 9
2 11
2 23
20 23
10 19
17 19
14 20
9 20
14 18
20 22
3 22
6 12
16 26
0 15
17 25
13 26
7 23
17 26
3 5
12 14
2 4
15 20
9 24
4 25
16 23
2 24
21 24

4 3 2 4 3 4 3 0 4 3 4 3 2 4 1 3 2 4 2 3 2 4 3 1 3 4 3