给定一个包含 $n$ 个节点和 $m$ 条边的连通无向图。每个节点 $u$ 都有一个邻居的有序列表 $l_u$，以及一个指向其邻居之一的指针 $p_u$。初始时，$p_u$ 指向 $l_u$ 中的第一个邻居。

你从节点 $s$ 出发，并无限次重复以下过程：

1. 设 $v$ 为你当前所在的节点。从 $v$ 移动到 $p_v$。
2. 将 $p_v$ 循环递增到 $l_v$ 中的下一个邻居。

请参阅样例说明以了解该过程的示例。 考虑在整个过程中列表 $p_1, p_2, \dots, p_n$ 以及当前节点 $c$ 的状态。我们将此称为一个“状态”。 输出任何一个出现无限次的状态。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。接下来是各测试用例的描述。 每个测试用例的第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n \le 2 \cdot 10^5, n - 1 \le m \le 4 \cdot 10^5, 1 \le s \le n$)，分别表示图中的顶点数、边数和起始节点。 接下来的 $n$ 行中，第 $u$ 行描述了节点 $u$ 的邻居有序列表 $l_u$。该行以一个整数 $k_u$ ($1 \le k_u < n$) 开头，表示 $u$ 的邻居数量。随后是 $k_u$ 个不同的整数 $v_1, v_2, \dots, v_{k_u}$ ($1 \le v_i \le n, v_i \neq u$)，表示 $u$ 的邻居。

保证如果 $v$ 是 $u$ 的邻居，则 $u$ 也是 $v$ 的邻居。同时保证图中总共有 $m$ 条无向边。 在所有测试用例中，保证 $\sum n \le 2 \cdot 10^5$，且 $\sum m \le 4 \cdot 10^5$。

输出格式

对于每个测试用例，以 $c \ p_1 \ p_2 \dots p_n$ 的格式输出任何一个无限重复的状态。

样例

输入 1

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

输出 1

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

说明

让我们可视化第三个样例。红色节点代表你当前的位置，从每个节点 $u$ 指出的箭头指向节点 $p_u$。以下是该过程开始时以及接下来的 8 个步骤后的图示：

我们可以看到，在执行了 8 次操作后，我们回到了初始状态 $p_1 = 4, p_2 = 1, p_3 = 2, p_4 = 3$，且当前位置（节点 1）与开始时相同。因此，一个有效的答案是直接输出初始状态。