Sparse Graph

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.

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.

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.

1
2 0
1

1

2016 ACM/ICPC Asia Regional Dalian Online