# Sparse Graph

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

## Description

In graph theory, the $complement$ of a graph $G$ is a graph $H$ on the same vertices such that two distinct vertices of $H$ are adjacent if and only if they are $not$ adjacent in $G$.

Now you are given an undirected graph $G$ of $N$ nodes and $M$ bidirectional edges of $unit$ length. Consider the complement of $G$, i.e., $H$. For a given vertex $S$ on $H$, you are required to compute the shortest distances from $S$ to all $N-1$ other vertices.

## Input

There are multiple test cases. The first line of input is an integer $T(1\le T<35)$ denoting the number of test cases. For each test case, the first line contains two integers $N(2\le N\le 200000)$ and $M(0\le M\le 20000)$. The following $M$ lines each contains two distinct integers $u, v(1\le u,v\le N)$ denoting an edge. And $S\ (1\le S\le N)$ is given on the last line.

## Output

For each of $T$ test cases, print a single line consisting of $N-1$ space separated integers, denoting shortest distances of the remaining $N-1$ vertices from $S$ (if a vertex cannot be reached from S, output -1" (without quotes) instead) in ascending order of vertex number.

## Sample Input

1
2 0
1

## Sample Output

1

wange2014

## Source

2016 ACM/ICPC Asia Regional Dalian Online