题目描述

给出一个 $n$ 个节点的树，编号为 $1$ 到 $n$。树的结构由 $n-1$ 条边表示，每条边 $a \rightarrow b$ 表示节点 $a$ 是节点 $b$ 的父节点。请找出这棵树的根节点，并输出每个节点的父节点以及高度。根节点的高度定义为 $1$，其他节点的高度为其父节点的高度加 $1$。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示树的节点数。

接下来的 $n-1$ 行，每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq n$），表示 $a$ 是 $b$ 的父节点。

输出格式

第一行输出根节点的编号，格式为 root:x，其中 $x$ 是根节点的编号。

接下来的 $n$ 行，每行包含三个整数，按照节点编号从小到大的顺序输出每个节点的信息：节点编号、父节点编号和高度，用空格分隔。根节点的父节点定义为其本身。

样例

样例输入

8
2 1
2 3
3 4
4 5
1 6
1 7
1 8

样例输出

root:2
1 2 2
2 2 1
3 2 2
4 3 3
5 4 4
6 1 3
7 1 3
8 1 3

数据范围与提示

• 数据范围：
  • 对于 30% 的数据，$n \leq 100$。
  • 对于 60% 的数据，$n \leq 1000$。
  • 对于 100% 的数据，$n \leq 10^5$。