分数: 300 点
问题陈述
有一棵树 T 与 N 顶点。的 i第边缘 (1\leq i\leq N-1) 连接顶点 U_i 和顶点 V_i.
给你两个不同的顶点 X 和 Y in T。 列出从顶点开始的简单路径上的所有顶点 X 到顶点 Y 按顺序,包括端点。
可以证明,对于任意两个不同的顶点 a 和 b 在树中,有一条唯一的简单路径 a to b.
什么是简单路径?
对于顶点 图表中的 X 和 Y 在图表中 G,一个 路径 从顶点 X 到顶点 Y 是一系列顶点 v_1,v_2, \ldots, v_k 这样 v_1=X, v_k=Y,和 v_i 和 v_{i+1} 由每个边缘连接 1\leq i\leq k-1。 另外,如果所有 v_1,v_2, \ldots, v_k 是不同的,路径被称为 简单路径 从顶点 X 到顶点 Y.约束
- 1\leq N\leq 2\times 10^5
- 1\leq X,Y\leq N
- X\neq Y
- 1\leq U_i,V_i\leq N
- 输入中的所有值都是整数。
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
输出
打印从顶点开始沿简单路径的所有顶点的索引 X 到顶点 Y 按顺序排列,中间有空格。
示例输入 1
5 2 5 1 2 1 3 3 4 3 5
示例输出 1
2 1 3 5
树 T 如下所示。从顶点出发的简单路径 2 到顶点 5 is 2 \to 1 \to 3 \to 5.
因此, 2,1,3,5 应按此顺序打印,中间有空格。

示例输入 2
6 1 2 3 1 2 5 1 2 4 1 2 6
示例输出 2
1 2
树 T 如下所示。
