题目描述

DFS 序是：在进行深度优先遍历时，按节点第一次被访问的顺序输出的节点编号序列。 欧拉序是：在进行深度优先遍历时，进入节点时记录一次；每遍历完本节点的一棵子树后，返回到本节点时都再记录一次；最终得到的节点编号序列。 现在给你一棵n个节点的树，节点编号1~n。请分别输出这棵树的 DFS 序和欧拉序。

输入格式

第一行为两个正整数n，s，表示这颗树有n个节点，编号 s 是根节点。 接下来的 n-1 行，每行两个整数u、v，表示u、v（0<u,v<=n）有一条边相连。

输出格式

输出二行。第一行是树的DFS 序。第二行是树的欧拉序。

样例

输入样例 1

5
1 2
2 4
4 5
2 3

输出样例 1

1 2 4 5 3
1 2 4 5 4 2 3 2 1

输入样例 2

4
1 2
2 3
3 4

输出样例 2

1 2 3 4
1 2 3 4 3 2 1

输入样例 3

5
1 2
1 3
1 4
1 5

输出样例 3

1 2 3 4 5
1 2 1 3 1 4 1 5 1

提示

数据规模：n<=100000，0<u,v<=n。