1523：嗅探器

题目描述

某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络，蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息，但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。现在需要你尽快地解决这个问题，应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获？

输入格式

输入的第一行一个整数 $n$，表示蓝军网络中服务器的数目。

接下来若干行是对蓝军网络的拓扑结构描述，每行是两个整数 $i, j$，表示编号为 $i$ 和编号为 $j$ 的两台服务器间存在连接（显然连接是双向的），服务器的编号从 $1$ 开始，一行两个 $0$ 表示网络的拓扑结构描述结束，再接下来是两个整数 $a, b$，分别表示两个中心服务器的编号。

输出格式

输出编号。如果有多个解输出编号最小的一个，如果找不到任何解，输出 No solution。

样例

样例输入 #1

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

样例输出 #1

1

样例解释 #1

• 服务器数 $n=5$。
• 连接关系（双向）：
  1. $2-1$
  2. $2-5$
  3. $1-4$
  4. $5-3$
  5. $2-3$
  6. $5-1$
• 以 0 0 结束边输入。
• 两个中心服务器编号：$a=4$，$b=2$。
• 需要在某个服务器上安装嗅探器，使得所有从 $4$ 到 $2$ 的数据包都经过该服务器（即该服务器是 $4$ 到 $2$ 的所有路径的必经点）。
• 服务器 $1$ 满足条件：所有从 $4$ 到 $2$ 的路径必须经过 $1$（因为 $4$ 只与 $1$ 相连，$1$ 连接 $2$ 和 $5$，但 $5$ 到 $2$ 不经过 $1$？检查：$4 \to 1 \to 2$ 是一条路径，$4 \to 1 \to 5 \to 2$ 是另一条，两条都经过 $1$）。所以安装 $1$ 可以捕获所有数据包。
• 输出 $1$。

数据范围

• $1 \le n \le 100$

时空限制

• 时间限制：1000 ms
• 内存限制：562144 KB

注意：本题是求无向图中两点间所有路径的必经点（割点）。可以先从 $a$ 开始 DFS，记录每个点的 $dfn$ 和 $low$，然后检查每个点 $u$（$u \neq a, u \neq b$）是否为割点，并且满足：删除 $u$ 后，$a$ 和 $b$ 不连通。但注意，不是割点也可能是必经点（比如 $a$ 或 $b$ 的邻接点）。更通用的方法是：从 $a$ 开始 DFS，记录每个点的前驱，然后枚举每个点 $u$（$u \neq a, u \neq b$），暂时删除 $u$（标记为不可访问），然后检查 $a$ 是否能到达 $b$，如果不能则 $u$ 是必经点。由于 $n \le 100$，可以枚举每个点并运行 DFS/BFS 检查连通性。注意需要输出编号最小的解。