Salaries

Memory limit: 128 MB

The Byteotian Software Corporation (BSC) has 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 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.

Input

In the first line of the standard input a single integer () is given that denotes the number of BSC employees. The employees have id's that range from 1 to .

The lines that follow provide information on these employees. The line no. describes the employee no. by two integers and (, ), separated by a single space. The number is the id of the direct supervisor of the employee . If , then is the CEO of BSC. If , then that is the salary of the employee . If, on the other hand, , then the salary of employee is not disclosed. Those '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 holds in addition.

Output

Your program should print lines to the standard output, each line holding a single integer. If the employee 's salary is disclosed or can be inferred from disclosed salaries, then the -th line should hold employee 's salary. Otherwise the -th line should contain .

Example

For the input data:

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

the correct result is:

2
10
1
9
5
8
0
0
0
0

Explanation of the example: The figure illustrates the hierarchy of employees. The encircled numbers are employee id's, whereas the numbers in italics given next to them (if any) are their disclosed salaries. The employee 3 has to earn 1 bythaler, and employee 6 has to earn 8 bythalers. The salaries of employees 7, 8, 9 and 10 cannot be uniquely determined from disclosed salaries.

Task author: Adam Karczmarz.