奶牛解渴

奶牛解渴

测试数据来自 wjszez/1543

【问题描述】
从1..N (3 <= N <= 99999; N为奇数)的分支管道输送干净的冷水。冷水通过管道流动时,夏日的高温使它变热了。Bessie想得到最凉的水,这样在这个夏天它会过得比其它奶牛惬意。
它绘制了全部的管道图并且注意到是一个树状结构,根结点在农场里,且每个结点如果有分支结点都一定有两个分支结点。令人惊奇的是,每根管子的长度都是1个单位,当然,N个管子都连到管道树上。
给出所有管道的连接图,求各个管道的分支点和终点到谷仓的距离表。Bessie将用这张表找到最冷的水。
管道的终点,可能是一个分支点也可能是龙头,用管道号命名。 管道图有C (1<= C <= N)个连结点,每个连结点有三个整数:管道号E_i (1 <= E_i <= N)和它的两个分支管道号B1_i和B2_i(2 <= B1_i <= N; 2 <= B2_i <= N)。管道1连接谷仓; 它到谷仓的距离是1。
【输入格式】
第一行:两个用空格隔开的整数N和C
第 2..C+1行: 第i+1行有三个用空格隔开的整数 E_i, B1_i, 和 B2_i
【输出格式】
第1..N行:第i行一个整数表示管道i的终点到谷仓的距离
【样例输入】
5 2
3 5 4
1 2 3
输入说明:
下面是管道图:

+------+
| Barn |
+------+
| 1
*
2 / \ 3
*
4 / \ 5

【样例输出】
1
2
2
3
3

信息

ID
1955
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者