Migrated from Lutece 3004 老大哥在看着你

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

2077年，老大哥终于完成了让所有人类住在同一颗世界树上的壮举。 世界树上共有 $n$ 为住户，其中标号为 $1$ 的住户就是老大哥，老大哥住在整棵树的根节点。除老大哥外，其余每个住户都有他的上级住户，这些住户与他的上级住户之间存在着一定距离，如此以来所有住户共同构成了这课世界树。 由于老大哥不希望住户做坏事，他想要让住户之间相互督查。因此，老大哥希望住户们离得近一些。现在，老大哥想要知道每位住户与离他最远的住户之间的最短距离是多少。你能帮老大哥算出结果吗？

Input

第一行一个整数 $n$，代表住户数量 接下来 $n-1$ 行每行两个整数。其中第 $i$ 行的第一个整数 $f_i(f_i \leq i)$ 表示第 $i+1$ 号住户的上级住户标号，第二个整数 $d_i$ 表示该住户与他的上级住户之间的距离

Output

输出 $n$ 行，每行一个整数。其中第 $i$ 行的整数表示离 $i$ 号住户最远的住户与他的最短距离为多少

Samples

3
1 1
1 5

5
6
6

Constraints

$3 \leq n \leq 1000000$ $f_i \leq i$ $1 \leq d_i \leq 1000$

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming