1350 - 子树大小与结点深度1

给出一棵树,求树中每棵子树的大小以及每个结点的深度。

输入

第1行,一个整数n,表示数的结点个数。(n <= 100)


接下来的 n - 1 行,每行两个整数x、y,表示y是x的孩子(x, y <=1000)


每行中两个数字之间用一个空格分隔。


输出

共n行,第i行为两个正整数,分别表示以结点i为根的子树大小和该结点i的深度。

样例

输入

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

输出

1 5
1 5
8 1
1 5
4 4
1 3
7 2
5 3

来源

题目参数

时间限制 1 秒
内存限制 32 MB
提交次数 0
通过人数 0
统计

上一题 下一题