As recent studies suggest, good relationships between employees and their supervisors have significant impact on their productivity and overall satisfaction. A positive attitude also helps to improve interpersonal communication, resolve problems and mitigate many potential conflicts. Establishing of such a positive relationship is often prevented by the unnecessary tension that arises between employees and their bosses, because at work, well, the boss is the boss and he has to be always right.
The Human Resources department of A Company that Makes Everything (ACME), Ltd. decided to relieve this tension by organizing various social events. One of their biggest projects is to get all employees of the company to play a game of Urvi Komu Urvi. The game is played by two teams of equal size and has been shown to be a great game for improving personal relationships, especially between people in different teams.
ACME has N employees organized in a hierarchical structure. Every employee has exactly one boss, except for the Director, who has no boss. A programmer would say that the structure is a tree with the Director being its root.
The ACME HR department now faces a challenging task: divide employees optimally into two teams to play the Urvi Komu Urvi game. By empirical research, they determined that if an employee x plays against his or her immediate boss y (i.e. x and y play in different teams), the tension of the employee x improves by the value tx. The tension of the Director cannot be improved in this way. The goal of the HR folks is to make teams so that
Fortunately, N is even, so it is possible to satisfy the first two conditions. On the other hand, the third condition seems to be very hard, and after spending a few days, they were still not able to find an optimal division. And, as you certainly suspect, we ask you to help them with this difficult task.
The first line of the input file contains a single even number N. The next N lines describe employees. The (i+1)-st line corresponds to the employee i. and contains two numbers b and t, where b is the boss of the employee i and t is the amount of the tension relieved if employee i plays against his or her boss. For the Director, both b and t are 0.
The output file describes a possible division of employees into teams. In particular, it should contain N/2 numbers separated by spaces and/or end of line characters. These numbers correspond to members of one team (the other team consists of all employees who are not in the first team). If there is more than one optimal solution, output any (only one) of them.
8 0 0 1 20 1 4 1 13 2 10 2 12 3 15 3 5
Output file:
1 3 5 6