题目描述

一所学校前一段时间买了第一台计算机（所以这台计算机的 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}$