Salaries

A company has $n$ employees arranged in a strict hierarchy. Every employee except the CEO has exactly one direct supervisor, and the CEO is the (direct or indirect) supervisor of everyone else. Each employee earns a distinct monthly salary, and these salaries are exactly the integers from $1$ to $n$. Every supervisor earns strictly more than each of their subordinates.

Some salaries are publicly disclosed. By law, whenever an employee's salary is disclosed, the salary of their direct supervisor is disclosed as well.

Determine every salary that is not disclosed but is nonetheless uniquely determined by the disclosed salaries together with the hierarchy.

The first line contains an integer $n$ ($1 \le n \le 10^6$), the number of employees, numbered from $1$ to $n$.

Each of the next $n$ lines describes one employee. Line $i+1$ contains two integers $p_i$ and $z_i$ ($1 \le p_i \le n$, $0 \le z_i \le n$). Here $p_i$ is the id of employee $i$'s direct supervisor; if $p_i = i$ then employee $i$ is the CEO. If $z_i > 0$ it is the disclosed salary of employee $i$; if $z_i = 0$ the salary of employee $i$ is not disclosed. All positive values $z_i$ are pairwise distinct.

The input is always consistent: at least one salary assignment agrees with both the hierarchy and the disclosed values.

Print $n$ lines. On line $i$ print employee $i$'s salary if it is disclosed or can be uniquely inferred from the disclosed salaries; otherwise print $0$.