题目背景

某网络实验室中有 $n$ 台路由器，实验员会为每次实验提前写好一份全局路由表。

每台路由器有唯一编号，编号范围为 $[1,n]$。路由表中的信息按写入顺序编号，编号越小表示越早写入。

所有路由器严格按照该路由表进行转发。

题目描述

给定 $n$ 台路由器、$m$ 条路由信息，以及起点 $x$。

第 $i$ 条路由信息为 $(u_i, v_i)$，表示 $u_i$ 与 $v_i$ 之间可双向转发。

每次实验只给定一张全局路由表，所有路由器都严格依据这张表进行转发。

设起点 $x$ 初始已收到数据包。若某条路由信息 $(u_i, v_i)$ 的一端最终能够收到数据包，则另一端也能够收到。不断应用该规则，直到状态不再变化。

记所有最终能收到数据包的路由器集合为 $S$（其中一定包含 $x$）。

你需要输出 $S$ 中除 $x$ 外的所有路由器编号，输出顺序由路由表决定：

• 按 $i \in [1,m]$ 依次扫描路由信息 $(u_i, v_i)$；
• 若 $u_i \in S$、$v_i \ne x$，且 $v_i$ 尚未输出，则输出 $v_i$；
• 若 $v_i \in S$、$u_i \ne x$，且 $u_i$ 尚未输出，则输出 $u_i$。

输入格式

第一行一个整数 $T$（$1 \le T \le 10^4$），表示实验次数。

接下来共 $T$ 次实验。第 $i$ 次实验的数据格式为：

• 第一行输入三个整数 $n, m, x$
• 接下来 $m$ 行，每行两个整数 $u_i, v_i$，表示第 $i$ 条路由信息。

输出格式

对每次实验输出一行：

• 输出所有最终收到数据包的路由器（不含 $x$），按上述“路由表扫描顺序”输出，空格分隔；
• 若不存在这样的路由器，输出 None。

样例

样例输入

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

样例输出

4 1 5 6 3
None

样例说明

• 第 1 组可用下图理解（括号中是路由表编号）：

4 --(1)-- 2 --(2)-- 1
|                     |
(3)                 (6)
|                     |
5 --(5)-- 6 --(4)-- 3

起点为 $x=2$，先求最终可达集合：

• 由 $(1)\ 2-4$ 可达 $4$
• 由 $(2)\ 1-2$ 可达 $1$
• 由 $(3)\ 4-5$ 可达 $5$
• 由 $(5)\ 5-6$ 可达 $6$
• 由 $(4)\ 3-6$ 可达 $3$

因此最终可达集合为 $\{1,2,3,4,5,6\}$。

再按路由表从 $[1,m]$ 扫描并按规则输出（去重且不输出 $x$）：

• 扫描 $(1)\ 2-4$：输出 $4$
• 扫描 $(2)\ 1-2$：输出 $1$
• 扫描 $(3)\ 4-5$：输出 $5$
• 扫描 $(4)\ 3-6$：先输出 $6$，再输出 $3$
• 扫描 $(5)\ 5-6$、$(6)\ 2-3$：两端都已输出，不再输出

最终输出 $4\ 1\ 5\ 6\ 3$。

• 第 2 组中，$x=3$ 不在任何路由信息中，最终只有 $3$ 自身可达，因此输出 None。

数据范围与约定

• $1 \le T \le 10^4$
• $1 \le n \le 2 \times 10^5$
• $0 \le m \le 2 \times 10^5$
• $1 \le x \le n$
• $1 \le u_i, v_i \le n$
• 所有实验的 $n$ 之和不超过 $2 \times 10^5$
• 所有实验的 $m$ 之和不超过 $2 \times 10^5$