题目描述

某学校在一段时间前购买了第一台计算机（因此这台计算机的编号是 1）。在最近几年中，学校又购买了 N-1 台新计算机。每台新计算机都连接到之前已经安装的计算机之一。学校的管理人员对网络运行缓慢感到担忧，想知道每台计算机需要发送信号的最大距离 S_i（即到最远计算机的电缆长度）。你需要提供这些信息。

提示：示例输入对应于此图。从图中可以看到，计算机 4 是距离计算机 1 最远的，因此 S_1 = 3。计算机 4 和 5 是距离计算机 2 最远的，因此 S_2 = 2。计算机 5 是距离计算机 3 最远的，因此 S_3 = 3。我们还得到 S_4 = 4，S_5 = 4。

输入格式

输入文件包含多个测试用例。每个用例的第一行是自然数 N（N <= 10000），接下来的 N-1 行描述了计算机的连接情况。第 i 行包含两个自然数——第 i 台计算机连接的计算机编号和用于连接的电缆长度。电缆的总长度不超过 10^9。输入行中的数字由空格分隔。

输出格式

对于每个用例，输出 N 行。第 i 行必须包含第 i 台计算机的数值 S_i（1 <= i <= N）。

输入输出样例 #1

输入 #1

输出 #1