You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

吉利学院成立以来有着许多学生，每一位学生都有许多朋友，这使得他们之间形成了一份十分复杂的关系网。

现由一位校外人员老秦，他知道了一则惊人的消息，而他想让吉利学院所有的学生都知道这个消息。

学生之间会相互传递消息：

• 当一位学生收到消息的时候，他可以给任意数量的手机联系人发送消息。
• 学生给朋友发消息不耗费任何代价。
• 学生给不是朋友的学生发消息需要花费 $1$ 的代价。
• 学生的朋友一定在他的手机联系人中。

现在老秦在不花费代价的情况下，把消息告诉学生 $s$ 。

随后老秦要进行 $n$ 轮游戏，对于第 $i$ 轮游戏，你需要输出一个整数，表示学生 $i$ 第一次知道消息时，整个学校的学生总共花费了多少代价，你必须最小化这个代价。

输入格式

输入一个整数 $T(1 \leq T \leq 10^3)$ ,表示测试样例组数。

对于每组测试样例：

第一行三个整数 $n(1 \leq n \leq 2 \times 10^5)$ ，$s(1 \leq s \leq n)$ ，$m(0 \leq m \leq min( \frac{n*(n-1)}{2} , 2 \times 10^6 )$ ，分别表示学校一共有 $n$ 名学生，被老秦发消息的学生 $s$ 和 $m$ 对朋友。

随后 $m$ 行，每行输入两个整数 $a,b(1 \leq a,b\leq n,a \neq b)$ 表示学生 $a$ 和学生 $b$ 是朋友，保证输入无重复朋友对。

随后 $n$ 行，第 $i$ 行：

• 首先输入一个整数 $k(0 \leq k \leq n-1)$ ，表示学生 $i$ 的非朋友手机联系人有 $k$ 名。
• 随后输入 $k$ 个互不相同的整数 ${a_1},{a_2},{a_3},...,{a_k}$ ，其中第 $j$ 个整数表示学生 ${a_j}$ 在学生 $i$ 的手机联系人中，保证 $1 \leq {a_j} \leq n,{a_j} \neq i$ 并且不包含学生 $i$ 的朋友。

多组数据范围保证，$\sum n ,\sum k \leq 2 \times 10^5 ,\sum m \leq 2 \times 10^6$ 。

输出格式

对于每组测试样例。

输出一行， $n$ 个整数，分别表示第 $i$ 轮游戏的最小代价。

特别的，对于无法得到答案的游戏，你需要输出 -1 。

输入输出样例 #1

输入 #1

1
6 1 2
1 2
3 4
1 3
0
1 5
0
0
0

输出 #1

0 0 1 1 2 -1