题目描述

现在有一棵 $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 \sim 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