题目描述

现在有一棵 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，表示结点 x 和 y 之间有一条边。（不保证 x 是 y 的父）

输出格式

输出有 n 行。

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

样例 #1

样例输入 #1

6
1 2
5 2
2 3
4 2
5 6

样例输出 #1

6 1
5 2
1 3
1 3
2 3
1 4