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

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

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

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

例如，上图中距离计算机 1 最远的是计算机 4，因此 $𝑆_1=3$；距离计算机 2 最远的是计算机 4 和 5，因此 $𝑆_2=2$；距离计算机 3 最远的是计算机5，所以 $𝑆_3=3$；同理，我们也得到 $𝑆_4=4，𝑆_5=4$。

输入格式

输入包含多测试数据。

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

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

输出格式

每组测试数据输出 N 行。

第 i𝑖 行输出第 i 台电脑的 $𝑆_𝑖$。

数据范围

$1≤𝑁≤10000,$ 电缆总长度不超过$10_9$

输入样例：

5
1 1
2 1
3 1
1 1

输出样例：

3
2
3
4
4