题目描述

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

输入格式

第一行有一个整数n，代表结点的数量，结点的编号为1~n。（1≤n≤100）

接下来有n-1行，每行有2个整数x，y，表示结点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

说明/提示

时间1000ms，内存256MiB