说明

现在有一棵 $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$ 对应的结点的深度。