题目描述

The Byteotian Software Corporation (BSC) has $n$ employees.

In BSC's strict hierarchy, each employee has a direct supervisor, except the CEO, to whom all other BSC employees answer, directly or not.

Each employee has a unique monthly salary, and all their salaries range from 1 to $n$ bythalers.

Each supervisor earns more than each of their subordinates.

According to Byteotian law, the salaries of employees on certain posts may be publicly disclosed.

Furthermore, if the salary of an employee is disclosed, then the salary of their supervisor is also disclosed.

The Byteotian Internal Revenue Anti-Corruption Service (BIRAS) has decided to investigate BSC.

Before BIRAS enters BSC with a warrant, they intend to learn the salaries of all BSC employees that are not disclosed but can be determined from those that are disclosed.

给出一棵n个结点的有根树，结点用正整数1~n编号。

每个结点有一个1~n的正整数权值，不同结点的权值不相同，

并且一个结点的权值一定比它父结点的权值大（根结点的权值最大，一定是n）。

现在有些结点的权值是已知的，并且如果一个结点的权值已知，它父结点的权值也一定已知。

问还有哪些结点的权值能够唯一确定。

输入格式

In the first line of the standard input a single integer $n$ ($1\le n\le 1\ 000\ 000$) is given that denotes the number of BSC employees.

The employees have id's that range from 1 to $n$.

The $n$ lines that follow provide information on these employees.

The line no. $i+1$ describes the employee no. $i$ by two integers $p_i$ and $z_i$ ($1\le p_i\le n$, $0\le z_i\le n$), separated by a single space.

The number $p_i$ is the id of the direct supervisor of the employee $i$.If $p_i=i$, then $i$ is the CEO of BSC. If $z_i>0$,then that is the salary of the employee $i$.If, on the other hand,$z_i=0$, then the salary of employee $i$ is not disclosed.Those $z_i$'s that are positive are also pairwise different.

The input data will always be such that there is at least one assignment of salaries to employees consistent with them, i.e., with the hierarchy and the partial assignment that they provide.

In tests worth 54% of the total points the condition $n\le 10\ 000$ holds in addition.

输出格式

Your program should print $n$ lines to the standard output, each line holding a single integer.

If the employee $i$'s salary is disclosed or can be inferred from disclosed salaries, then the $i$-th line should hold employee $i$'s salary.

Otherwise the $i$-th line should contain $0$.

10
2 2
2 10
1 0
2 9
2 5
4 0
6 0
6 0
5 0
5 0

2
10
1
9
5
8
0
0
0
0

提示

给出一棵n个结点的有根树，结点用正整数1~n编号。

每个结点有一个1~n的正整数权值，不同结点的权值不相同，

并且一个结点的权值一定比它父结点的权值小（根结点的权值最大，一定是n）。

现在有些结点的权值是已知的，并且如果一个结点的权值已知，它父结点的权值也一定已知。

问还有哪些结点的权值能够唯一确定。