题目描述

给出一棵\(n\)个节点的树，节点编号为\(1 \sim n\)（根节点编号为\(1\)）。对于每一个叶子节点，输出从根到叶子的路径。

注意：按照路径的字典序从小到大输出。

格式

输入格式

第一行：\(1\)个数\(n\)，表示树的节点数量。

后面\(n-1\)行：每行\(2\)个数\(x \ y\)，表示节点\(x\)是节点\(y\)的父节点。

输出格式

输出行数等于叶子节点的数量，每行对应从根到叶子节点的路径。路径中的数字为经过节点的编号。按照路径的字典序从小到大输出。

样例1

样例输入1

5
1 2
1 3
2 4
4 5

样例输出1

1 2 4 5
1 3

样例解释

\(3\) 和 \(5\) 为叶子结点，对应的路径分别为\(1 \ 3\)和\(1 \ 2 \ 4 \ 5\)，后者的字典序更小，因此输出结果为：
\(1 \ 2 \ 4 \ 5\)
\(1 \ 3\)

限制

\(100\%\)的数据： \(3 \le n \le 2000， 1 \le x, y \le n\)。