说明

现在有一棵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。（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