#2583. 最远距离

最远距离

Description

学校不久前买了第11台计算机(编号为11)。近年来,学校又买了N1N-1台新计算机。每台新计算机都被连接到先前安装的一台计算机上。学校管理者担心网络运行缓慢,想知道第i台计算机发送信号的最大距离sis_i(即电缆到最远的计算机的长度)。

image

提示:输入样例对应上图,可以看出,计算机11距离44最远,最远电缆长度为33,所以s1=3s_1=3。计算机22距离5544最远,最远电缆长度s2=2s_2=2。计算机33距离55最远,最远电缆长度s3=3s_3=3。同理,得到s4=4s_4=4s5=4s_5=4

Format

Input

输入包含多个测试用例。每个测试用例的第1行都为nn10000n(n≤10000),后面n1n-1行为对计算机的描述。第i行包含两个自然数,分别表示连接第ii台计算机的计算机编号和用于连接的电缆长度。电缆总长度不超过10910^9

Output

对每个测试用例,都输出nn行,第ii行表示第ii台计算机到其他计算机的最远距离。对每个测试用例,都输出nn行,第ii行表示第ii台计算机到其他计算机的最远距离。

Samples

5
1 1
2 1
3 1
1 1
3
2
3
4
4

来源

HDU2196