Problem C: Shortest path

Problem C: Shortest path

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1754  Solved: 220
[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]