Problem C: Shortest path Problem C: Shortest path
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 2534 Solved: 410
[Submit][Status][Web Board]Description
Alice has a graph of n nodes and m undirected edges. These nodes are numbered from 1 to n, and now she wants to know the shortest path from node s to other nodes. If there is no path between s and node i, output -1. (1 <= i <= n).
Input
The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be three integers, n(1 <= n <= 105), m(1 <= m <= 5*105) and s(1 <= s <= n). The following are m lines, and each line will be two integers x and y, which means there is an undirected edge between x and y.
Output
For each test, output numbers in one line. The i-th number means the shortest path between s and node i. If the path does not exist, then print -1 instead.
Sample Input
1
4 4 1
1 2
2 3
3 4
1 4
Sample Output
0 1 2 1
HINT
[Submit][Status]