这是一个通信问题。

一颗危险的地雷！

小青鱼非常喜欢扫雷游戏，他非常想在 Universal Cup 总决赛期间玩这个游戏。因此，他给你一个机会来体验另一个类似扫雷的游戏，叫做 CyanSweeper。这个游戏是在一个无向连通平面图上进行的，而不是在网格上。

为了玩这个游戏，他给你一个含有 $n$ 个顶点和 $m$ 条边的平面图。顶点从 $1$ 到 $n$ 进行编号。有 $k$ 个含有地雷的特殊顶点，游戏由两个阶段组成。

第一次运行。小青鱼给你该图以及 $k$ 个地雷顶点的编号 $b_1, b_2, \dots, b_k$。你必须生成一个数组 $a_1, a_2, \dots, a_n$，满足以下条件：

• 对于每个没有地雷的顶点 $v$，$a_v$ 必须等于 $v$ 的邻居中含有地雷的顶点个数（即标准的扫雷计数）。
• 对于每个含有地雷的顶点 $v$，$a_v$ 可以是 $\{1, 2, \dots, k\}$ 中的任意整数，但必须满足约束条件：地雷顶点处的数值 $a_{b_1}, a_{b_2}, \dots, a_{b_k}$ 构成 $\{1, 2, \dots, k\}$ 的一个排列。

除了数组 $a$ 之外，小青鱼还要求你向第二次运行传输一个长度最多为 100 的非空二进制字符串 $s$。

第二次运行。小青鱼给你相同的图（具有相同的顶点编号）、与第一次运行中生成的完全相同的数组 $a_1, \dots, a_n$，以及传输的二进制字符串 $s$。然而，你不会被告知地雷顶点的编号。你的任务是根据图、数组 $a$ 和传输的字符串 $s$，输出地雷顶点的集合。

请编写一个程序来玩 CyanSweeper。

输入格式

输入包含多组测试数据。输入的第一行包含两个整数 $r$ ($r \in \{1, 2\}$) 和 $T$ ($1 \le T \le 10$)，分别表示运行编号和测试数据组数。

对于每组测试数据：

• 如果 $r = 1$，第一行包含三个整数 $n, m, k$ ($1 \le k \le n \le 5 \times 10^5$，$n - 1 \le m \le 10^6$)。接下来的 $m$ 行每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，描述一条无向边。保证该图是连通的、简单的平面图。下一行包含 $k$ 个互不相同的整数 $b_1, b_2, \dots, b_k$ ($1 \le b_i \le n$)，表示地雷顶点的索引。
• 如果 $r = 2$，第一行包含两个整数 $n$ 和 $m$。接下来的 $m$ 行以相同的格式描述边。下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，即第一次运行中生成的解决方案。最后一行包含第一次运行解决方案传输的二进制字符串 $s$。

保证所有测试数据的 $n$ 之和不超过 $5 \times 10^5$，所有测试数据的 $m$ 之和不超过 $10^6$。

输出格式

如果 $r = 1$，对于每组测试数据，在一行中输出用空格分隔的数组 $a_1, a_2, \dots, a_n$，并在下一行输出二进制字符串 $s$。数组必须满足上述规则，且 $s$ 必须仅由字符 0 和 1 组成，长度在 $1$ 到 $100$ 之间。

如果 $r = 2$，对于每组测试数据，输出两行。第一行包含一个整数 $k$，表示地雷的数量。第二行包含 $k$ 个互不相同的整数，对应地雷顶点的索引。你可以以任意顺序输出地雷顶点的索引。报告的集合必须与对应的第一次运行输入中的地雷集合完全一致。

测试工具

提供了一个测试工具以帮助参赛者开发和测试他们的解决方案。你可以从 DOMjudge 系统下载此工具。使用 -h 参数运行该工具可以查看如何使用它。该测试工具仅实现部分测试场景以及真实评测程序的部分功能。