AT_abc417_e.[ABC417E] A Path in A Dictionary

给你一个简单相连的无向图 $G$ ，有 $N$ 个顶点和 $M$ 条边。顶点编号从 $1$ 到 $N$，第 $i$ 条边连接点 $U_i$ 和点 $V_i$。

在 $G$ 中，找出从顶点 $X$ 到顶点 $Y$ 的字典序最小的简单路径。

也就是说，在满足以下条件的整数序列 $P=(P_1,P_2,\ldots,P_{\lvert P\rvert})$ 中，找出一条字典序最小的路径：

• $1\leq P_i\leq N$
• 若 $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$ 个测试案例，请找出每个案例的答案。

::::info[整数序列的字典序]
如果下面的任意一个条件成立，则 $S$ 的字典序小于 $T$（下面用 $\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$。
   ::::

输入从标准输入流按照下列格式给出：

$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$ 行为从 $X$ 到 $Y$ 的字典序最小的简单路径，即第 $i$ 个测试数据的答案。

也就是说，如果第 $i$ 个测试数据的答案是 $P=(P_1,P_2,\ldots,P_{\lvert P\rvert})$ 时，在第 $i$ 行一次输出 $P_1$, $P_2$, $\ldots$, $P_{\lvert P\rvert}$，中间用空格隔开。

数据范围

• $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$
• 若 $i\neq j$, 则 $(U_i,V_i)\neq (U_j,V_j)$.
• 保证给定图联通
• 每个输入中所有测试数据的 $N$ 之和不超过 $1000$.
• 每个输入中所有测试数据的 $M$ 之和不超过 $5\times 10^4$.
• 所有输入均为整数.

样例解释

对于第一个测试数据，图 $G$ 如下：

在 $G$ 上，从点 $3$ 到点 $5$ 的简单路径按照字典序排列如下：

• $(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$ 的简单路径。