#1901. 子树的大小及深度

子树的大小及深度

题目描述

现在有一棵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个整数xy,表示结点x和y之间有一条边。(不保证x是y的父)

输出格式

输出有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