小泽要为一棵以顶点 $1$ 为根的树分配区间。对每个顶点 $i$，他需要确定两个正整数 $L_i$ 和 $R_i$，并把闭区间 $[L_i,R_i]$ 分配给顶点 $i$。

设 $S_i$ 表示以顶点 $i$ 为根的整棵子树所包含的顶点集合，所有区间必须满足：

• 如果 $S_i\subseteq S_j$，那么必须有 $[L_i,R_i]\subseteq[L_j,R_j]$；
• 如果 $S_i\cap S_j=\varnothing$，那么区间 $[L_i,R_i]$ 与 $[L_j,R_j]$ 也必须没有交集。

在满足条件的方案中，所有区间端点里出现的最大整数要尽可能小。由于最优方案可能不唯一，本题采用下面的固定输出约定：把每个顶点的孩子按编号从小到大访问，依次给深度优先遍历遇到的叶子分配 $[1,1],[2,2],\ldots$，每个内部顶点的区间取其所有孩子区间的最小左端点和最大右端点。

请按顶点编号输出按照上述约定得到的最优方案。

输入格式

第一行输入一个整数 $N$，表示树的顶点数量。

接下来 $N-1$ 行，每行输入两个整数 $u_i$ 和 $v_i$，表示顶点 $u_i$ 与顶点 $v_i$ 之间有一条边。

输出格式

输出 $N$ 行。第 $i$ 行输出两个整数 $L_i$ 和 $R_i$，表示分配给顶点 $i$ 的闭区间。

10
5 2
3 9
8 4
2 3
6 1
1 2
2 4
4 10
6 7

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

9
1 4
5 9
5 4
1 6
2 3
7 6
1 2
3 8

1 3
1 1
1 1
2 2
2 2
3 3
3 3
1 1
2 2

9
4 2
3 5
3 2
7 4
9 6
8 5
1 2
4 6

1 3
1 3
1 1
2 3
1 1
2 2
3 3
1 1
2 2

数据范围与约定

• $2\le N\le2\times10^5$
• 输入图是一棵树