题目描述

一所学校前一段时间买了第一台计算机（所以这台计算机的 ID 是 1）。

近年来，学校又购买了 $N$−1 台新计算机。

每台新计算机都与之前买进的计算机中的一台建立连接。

现在请你求出第 i 台计算机到距离其最远的计算机的电缆长度。

例如，上图中距离计算机 1 最远的是计算机 4，因此 $S_1$=3；距离计算机 2 最远的是计算机 4 和 5，因此 $S_2$=2；距离计算机 3 最远的是计算机 5，所以 $S_3$=3；同理，我们也得到 $S_4$=4，$S_5$=4。

输入格式

输入包含多测试数据。

每组测试数据第一行包含整数 $N$。

接下来 $N$−1 行，每行包含两个整数，第 $i$行的第一个整数表示第 $i$台电脑买入时连接的电脑编号，第二个整数表示这次连接花费的电缆长度。

输出格式

每组测试数据输出$N$ 行。

第 $i$行输出第 $i$ 台电脑的 $S_i$。

样例

5
1 1
2 1
3 1
1 1

3
2
3
4
4

数据范围

$1≤N≤10000$, 电缆总长度不超过$10^9$

来源

• HDOJ2196
• 算法竞赛进阶指南