说明

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

数据范围

• $n≤100$