2166 - 子树的大小及深度

题目描述

现在有一棵 n 个结点的树,结点 1 为这棵树的根,结点 1 的深度为 1,求出每棵子树的大小及每个结点的深度。

比如,有如下图所示的树:

该树中:

结点 1 对应的子树大小为 6,深度为 1

结点 2 对应的子树大小为 5,深度为 2

结点 3 对应的子树大小为 1,深度为 3

结点 4 对应的子树大小为 1,深度为 3

结点 5 对应的子树大小为 2,深度为 3

结点 6 对应的子树大小为 1,深度为 4

输入

输入有 n 行。

1 行有一个整数 n,代表结点的数量,结点的编号为1~n。(1≤n≤100

接下来有 n-1 行,每行有 2 个整数 x,y,表示结点 xy 之间有一条边。(不保证 xy 的父)

输出

输出有 n 行。

i 行输出 2 个整数,分别是以编号 i 为根的子树的大小,以及编号 i 对应的结点的深度。

样例

输入

6
1 2
5 2
2 3
4 2
5 6

输出

6 1
5 2
1 3
1 3
2 3
1 4
来源

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题