问题描述

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