Shortest Path in an Undirected Graph

You are given an undirected graph with N vertices and M edges. For each test case, you need to compute the shortest distance from a given source vertex S to every other vertex using the Breadth-First Search (BFS) algorithm.

Formally, let \(d(i)\) be the shortest distance from the source \(S\) to vertex \(i\) for \(1 \leq i \leq N\). Then, we define: \[ d(i)=\begin{cases}0,& \text{if } i=S,\\ d(i)=d(j)+1,& \text{if there exists an edge } (j,i),\\ -1,& \text{if vertex } i \text{ is not reachable from } S. \end{cases} \]

If a vertex is unreachable from the source, output -1 for that vertex.

inputFormat

The input is read from standard input and has the following format:

T
For each test case:
    N M
    u1 v1
    u2 v2
    ...
    uM vM
    S

Where:

• T is the number of test cases.
• N is the number of vertices.
• M is the number of edges.
• Each of the next M lines contains two integers u and v indicating there is an undirected edge between vertices u and v.
• S is the source vertex.

outputFormat

For each test case, output a single line containing N space-separated integers. The i-th integer represents the shortest distance from the source vertex S to vertex i. If vertex i is not reachable from S, output -1 for that vertex.

## sample

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

0 1 2 1

</p>