#558. Computer

Computer

题目描述

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

近年来,学校又购买了N1N-1台新计算机。

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

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

例如,上图中距离计算机 1 最远的是计算机 4,因此 S1=3S_1=3;距离计算机 2 最远的是计算机 4 和 5 ,因此 S2=2S_2=2;距离计算机 3 最远的是计算机 5 ,所以 S3=3S_3=3;同理,我们也得到 S4=4S_4=4S5=4S_5=4

输入格式

输入包含多测试数据。

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

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

输出格式

每组测试数据输出 NN 行。

ii 行输出第 ii 台电脑的 SiS_{i}

样例

输入样例:

5
1 1
2 1
3 1
1 1

输出样例:

3
2
3
4
4

数据范围与提示

数据范围

1N10000,1≤N≤10000,

电缆总长度不超过 10910^{9}