The president of a certain company would like to boost the morale of their employees by organizing citrus Thursdays. They cannot decide whether to order oranges or grapefruits, so they have decided that the employees themselves will make the decision.

The voting will proceed according to the company hierarchy. There are $n$ employees in the company, numbered from $1$ to $n$, including the president, who is numbered $1$. Each employee is either a manager or a regular employee, with the president always being a manager. Each manager has an odd number of direct subordinates, who may be either regular employees or other managers. Regular employees have no subordinates. Every employee except for the president (who has no supervisor) has exactly one direct supervisor. There are no cycles in the company hierarchy.

Each regular employee decides independently whether to vote for oranges or for grapefruits. Each manager votes the same way as the majority of their (direct) subordinates. The result of the vote depends on the president's vote.

Bajtazar owns an orange wholesale business and wants oranges to win the vote. Unfortunately, his good friend Bajtoni owns a grapefruit wholesale business and would prefer grapefruits to win. The friends have decided to play a game: they will take turns (starting with Bajtazar) choosing one regular employee with whom neither of them has spoken yet and convincing them to vote for their respective citrus (Bajtazar and Bajtoni are very persuasive). The game ends when they have spoken to all regular employees.

Help Bajtazar determine how to choose employees so that oranges ultimately win the vote. You may assume that the company hierarchy is such that Bajtazar can always (regardless of Bajtoni's moves) ensure a victory.

Interaction

You must implement a program that helps Bajtazar by using the provided library (which simulates Bajtoni's moves).

To use the library, include the following in your program: C/C++: #include "glolib.h" Python: from glolib import daj_n, daj_przelozonego, ruch

The library provides the following functions: daj_n() – This function returns an integer $n$, representing the number of employees in the company. daj_przelozonego(v) – This function returns the number of the direct supervisor of the employee with number $v$ (for $1 < v \le n$). The supervisor's number is always smaller than the employee's number. * ruch(x) – This function informs the library that Bajtazar is making his next move by choosing the regular employee with number $x$. The function returns the number of the employee chosen in the next move by Bajtoni. If Bajtazar's move was the last move in the entire game, the program will automatically terminate after this function is called (you may assume that Bajtazar will always make the last move).

You may use the functions daj_n and daj_przelozonego multiple times. Your program must not open any files or use standard input and output. It may use standard diagnostic output (stderr), but keep in mind that this consumes valuable time. Your solution will be compiled with the library using the following commands: C++: g++ -O3 -static -std=c++17 glolib.cpp glo.cpp Python: python3 glo.py

Note: The memory limit mentioned above applies only to your solution and therefore does not include the memory used by the library.

Subtasks

The test suite is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

Examples

Example 1

The following is a sample program execution for a test case where the company hierarchy looks as follows:

Input 1

7
1 2 1 1 2 2

Output 1

3
7
6

Note

If Bajtazar had talked to, for example, employee number 4 in his second move, he would have guaranteed himself a victory.

Evaluation Tests

• 1st evaluation: $n = 19$, the president has three managers under them, and each of them has five regular employees under them;
• 2nd evaluation: $n = 364$, each manager has exactly three people directly under them, and all regular employees are at the same distance from the president;
• 3rd evaluation: $n = 200\,000$, there are $100\,001$ managers in the company, each of them (except the president) is a direct subordinate of the manager with a number smaller by 1; furthermore, $99\,999$ regular employees are directly subordinate to the manager with number $100\,001$.

Implementation Details

Sample incorrect solutions along with sample libraries can be found in the dlazaw folder. The libraries may differ in behavior from those used by the graders and may not meet the problem requirements. They are only intended to show how to interact with the program.

Your solution, when compiled with the sample library, reads the description of the company hierarchy from standard input – the number $n$, followed by $n - 1$ numbers $p_2, \dots, p_n$, separated by spaces – where the value $p_i$ denotes the number of the direct supervisor of employee $i$. In the sample library, Bajtoni always convinces the regular employee with the smallest number who has not yet been convinced. The same strategy is used in the sample test and the evaluation tests in SIO. The sample library prints the subsequent moves made by Bajtazar and Bajtoni.