分数: 475 点
问题陈述
给你一个简单的连通无向图 G 与 N 顶点和 M 边缘。
的顶点 G 是编号的顶点 1,顶点 2, \ldots,顶点 N,和
的 i-th (1\leq i\leq M) 边连接顶点 U_i 和 V_i.
从顶点查找字典顺序最小的简单路径 X 到顶点 Y in G.
即找到整数序列中字典序最小的 P=(P_1,P_2,\ldots,P_{\lvert P\rvert}) 满足以下条件:
- 1\leq P_i\leq N
- If i\neq j,那么 P_i\neq P_j.
- P_1=X 和 P_{\lvert P\rvert}=Y.
- 对于 1\leq i\leq \lvert P\rvert-1,存在连接顶点的边 P_i 和 P_{i+1}.
可以证明,在该问题的约束下,这样的路径总是存在。
你被给予 T 测试用例,因此找到每个用例的答案。
整数序列的字典顺序
整数序列 S=(S_1,S_2,\ldots,S_{\lvert S\rvert}) 按字典顺序小于整数序列 T=(T_1,T_2,\ldots,T_{\lvert T\rvert}) 如果以下 1. 或 2. 之一成立。在这里, \lvert S\rvert 和 \lvert T\rvert 代表的长度 S 和 T。- \lvert S\rvert<\lvert T\rvert 和 (S_1,S_2,\ldots,S_{\lvert S\rvert})=(T_1,T_2,\ldots,T_{\lvert S\rvert}).
- 存在一些 1\leq i\leq \min(\lvert S\rvert,\lvert T\rvert) 这样 (S_1,S_2,\ldots,S_{i-1})=(T_1,T_2,\ldots,T_{i-1}) 和 S_i< T_i.
约束
- 1\leq T\leq 500
- 2\leq N\leq 1000
- N-1\leq M\leq \min\left( \frac{N(N-1)}{2},5\times 10^4\right)
- 1\leq X,Y \leq N
- X\neq Y
- 1\leq U_i<V_i \leq N
- If i\neq j,那么 (U_i,V_i)\neq (U_j,V_j).
- 给定的图形已连接。
- 总和 N 每个输入中的所有测试用例最多 1000.
- 总和 M 每个输入中的所有测试用例最多 5\times 10^4.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
\mathrm{case}_i 代表 i- 第一个测试用例。 每个测试用例均按以下格式给出:
N M X Y U_1 V_1 U_2 V_2 \vdots U_M V_M
输出
输出 T 行。
的 i第行 (1\leq i\leq T) 应包含简单路径上的顶点编号,即答案 i-第一个测试用例,按顺序排列,用空格分隔。
也就是说,当答案 i- 第一个测试用例是 P=(P_1,P_2,\ldots,P_{\lvert P\rvert}),
输出 P_1, P_2, \ldots, P_{\lvert P\rvert} 上 i按此顺序的第行,以空格分隔。
示例输入 1
2 6 10 3 5 1 2 1 3 1 5 1 6 2 4 2 5 2 6 3 4 3 5 5 6 3 2 3 2 1 3 2 3
示例输出 1
3 1 2 5 3 2
对于第一个测试用例,图 G 如下:

从顶点开始的简单路径 3 到顶点 5 on G按字典顺序列出如下:
- (3,1,2,5)
- (3,1,2,6,5)
- (3,1,5)
- (3,1,6,2,5)
- (3,1,6,5)
- (3,4,2,1,5)
- (3,4,2,1,6,5)
- (3,4,2,5)
- (3,4,2,6,1,5)
- (3,4,2,6,5)
- (3,5)
其中,按字典顺序最小的是 (3,1,2,5),所以输出 3,1,2,5 第一行以空格分隔。
对于第二个测试用例, (3,2) 是从顶点开始的唯一简单路径 3 到顶点 2.