路由表输出（router）

题目描述

Y 同学所在的实验室中有 $n$ 台路由器。每次实验开始前，实验员都会预先写好一张全局路由表。

每台路由器有唯一编号，编号范围为 $[1,n]$。路由表中共有 $m$ 条路由信息，按写入先后依次编号为 $1 \sim m$，编号越小表示越早写入。

给定起点路由器 $x$，其中第 $i$ 条路由信息记为 $(u_i,v_i)$，表示路由器 $u_i$ 与 $v_i$ 之间可以双向转发数据包。

现设起点路由器 $x$ 在初始时已经收到数据包。定义集合 $S$ 为所有最终能够收到数据包的路由器集合，其满足：

• 初始时，$x \in S$；
• 若存在某条路由信息 $(u_i,v_i)$，且 $u_i \in S$ 或 $v_i \in S$，则可将另一端也加入 $S$；
• 不断重复上述过程，直到集合 $S$ 不再发生变化。

你需要输出集合 $S$ 中除 $x$ 以外的所有路由器编号。

注意，输出顺序并不是搜索过程中第一次访问这些路由器的顺序，而是在整个集合 $S$ 确定之后，再按照路由表的写入顺序统一决定。

具体地，按 $i=1,2,\dots,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$，表示实验次数。

接下来共 $T$ 组实验数据。每组数据格式如下：

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

输出格式

对于每组实验，输出一行：

• 输出所有最终能够收到数据包的路由器（不含 $x$），按题目规定的顺序输出，相邻编号之间用一个空格分隔；
• 若不存在这样的路由器，则输出 None。

样例

样例输入 #1

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

样例输出 #1

4 1 5 6 3
None

样例解释

第 $1$ 组

起点为 $x=2$。

根据所有路由信息，可以确定最终能够收到数据包的路由器集合为：

也就是说，除起点 $2$ 以外，其余路由器最终都能够收到数据包。

接下来按照路由表的写入顺序依次扫描：

因此答案为：

4 1 5 6 3

第 $2$ 组

起点为 $x=3$。

路由表中只有一条路由信息 $(1,2)$，与路由器 $3$ 无关，因此最终只有路由器 $3$ 自身能够收到数据包，不存在其他需要输出的路由器。

因此输出：

None

数据范围与约定

对于 $100\%$ 的数据，保证：

• $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$。

• 特殊性质 A：保证 $m \le n-1$。
• 特殊性质 B：保证图中不存在重边。
• 特殊性质 C：保证所有路由器最终都能够收到数据包。