题目描述

给定一棵 $n$ 个结点的无根树，结点编号 $1\sim n$，边用「连接的两个端点」描述。我们规定 $1$ 号结点是根，并且按照「越靠近根深度越小」来定义深度：根的深度为 $0$，其余结点的深度为其父结点深度加一。

对每个结点 $u$，再定义它的子树大小 $sz_u$：以 $u$ 为根的子树（也就是 $u$ 以及 $u$ 的所有后代）里的结点个数。

请你求出每个结点的深度和子树大小。

输入格式

第一行一个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示结点 $u$ 与结点 $v$ 之间有一条边。保证这些边构成一棵树。

输出格式

共 $n$ 行。第 $i$ 行两个整数，依次表示结点 $i$ 的深度和子树大小，中间用一个空格隔开。

输入输出样例 #1

输入 #1

5
1 2
1 3
2 4
2 5

输出 #1

0 5
1 3
1 1
2 1
2 1

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 10^5$。