J9 实践-3 树上的简单路径

题目描述

有一棵树 $T$ 有 $N$个顶点。第 $i$ 条边$(1\leq i\leq N-1)$连接顶点 $U_i$ 和顶点 $V_i$。

在 $T$ 中为您提供了两个不同的顶点 $X$ 和 $Y$。按顺序列出从顶点 $X$ 到顶点 $Y$ 的简单路径上的所有顶点，包括端点。

可以证明，对于树中任意两个不同的顶点 $a$ 和 $b$，存在唯一的从 $a$ 到 $b$ 的简单路径。

输入格式

第一行三个整数，$N$，$X$，$Y$；

第二行到第 $N$ 行，每行表示一条边，两个整数顶点 $U_i$ 和顶点 $V_i$。

输出格式

只有一行，按顺序列出从顶点 $X$ 到顶点 $Y$ 的简单路径上的所有顶点，包括端点。

样例输入

5 2 5
1 2
1 3
3 4
3 5

样例输出

2 1 3 5

样例分析

样例 $1$ 如图所述，从 $2$ 号结点到 $5$ 号结点的简单路径 $2 \to 1 \to 3 \to 5$。

数据范围

对于 $100\%$ 的数据：$1\leq N\leq 2\times 10^5$。