← 返回题目列表

AtCoder · abc417_e

H. 字典中的路径

中文机器翻译题面 查看原题

分数: 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。
  1. \lvert S\rvert<\lvert T\rvert 和 (S_1,S_2,\ldots,S_{\lvert S\rvert})=(T_1,T_2,\ldots,T_{\lvert S\rvert}).
  2. 存在一些 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.