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 <= 10^{5}), m(1 <= m <= 5*10^{5}) 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]