题目描述

给出一个 $n$ 个节点的无根树，节点编号为 $1$ 到 $n$。通过 $n-1$ 条无向边描述树的结构，每条边以 $a\text{-}b$ 的形式给出，表示节点 $a$ 和节点 $b$ 之间有一条边。指定根节点为 $rt$，请计算每个节点的父节点和高度。其中：

• 根节点的父节点为自身，高度为 $1$；
• 其他节点的父节点为其在树中连接到根节点路径上的直接前驱节点，高度为父节点的高度加 $1$。

输入格式

第一行包含两个整数 $n$ 和 $rt$（$1 \leq n \leq 10^5$，$1 \leq rt \leq n$），分别表示节点数和根节点编号。
接下来的 $n-1$ 行，每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq n$），表示一条无向边。

输出格式

按节点编号从小到大的顺序，输出 $n$ 行，每行包含三个整数：节点编号、父节点编号、高度，用空格分隔。

样例

样例输入

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

样例输出

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$