题目描述

给你一棵树和树上的两个节点 $u,v(u≠v)$, 需要你求出从 $u$ 到 $v$ 的路径经过的所有节点。

树以下列方式给出：

• 输入第一行给出一个数 $n$，表示一共有 $n$ 个节点；
• 接下来 $n−1$ 行，每行给出两个数 $x,y(x≠y)$，表示 $x,y$ 之间有一条边。

输入最后一行两个数 $u,v$ 表示询问。

输入格式

见题面。

输出格式

输出一行，表示路径经过的节点，从 $u$ 开始到 $v$ 结束，节点编号用空格隔开。

4
1 2
1 3
3 4
2 4

2 1 3 4

数据规模

对于所有数据，保证$1≤n≤100000,1≤x,y,u,v≤n,u≠v,x≠y$。