1351 - 子树大小与结点深度2

给出一棵树,求树中每棵子树的大小以及每个结点的深度(假设结点1为根)。

输入

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


接下来的 n - 1 行,每行两个整数x、y,表示x结点和y结点之间有一条边,但不保证x是y的父结点。


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


输出

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

样例

输入

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

输出

8 1
1 4
3 3
1 4
4 2
1 2
1 3
2 2

来源

题目参数

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

上一题 下一题