Problem Description

你的机房共有 $n$ 台电脑，但是第 $k$ 台电脑坏了。

你的老师给你 $m$ 次要求，每次要求你将第 $u_i$ 和 $v_i$ 台电脑交换，这样坏的电脑就可能会被交换到一个新的位置。

但由于你希望进行暗箱操作，你可以拒绝执行其中的若干条要求，使得坏的电脑最终交换到 $j$ 号位置。

由于骗过老师很累，请对于 $j=1...n$ 求出最少可能的不执行要求条数，使得坏的电脑在第 $j$ 个位置。

Input

本题有多组测试数据。

第一行一个数 $T$ 表示一共有 $T$ 组数据。对于每一组数据：

第一行三个整数 $n, m, k$ ，表示电脑个数，总操作次数和坏电脑的初始位置。

下面 $m$ 行，每行两个正整数 $u_i$ , $v_i$ ，表示这次操作选择的两个位置。

满足 $1 \le T \le 5$，$1 \le n \le 10^5$，$0 \le m \le 10^5$，$1 \le k \le n$。

Output

对每组数据，输出共一行 $n$ 个整数，第 $i$ 个整数表示使坏电脑最终停留在该位置所需的最少暗箱操作次数。

若最终坏电脑不可能停留在该位置，则输出 $−1$。

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

2 0 3 1 -1