29846번 - Choice 다국어인터랙티브

To boost the morale of his employees, the CEO of a company decided to offer fresh fruits on Thursdays. He can't decide between apples and pears himself and lets employees vote.

There are $N$ employees in the company, numbered from $1$ to $N$. Each employee is either a manager who has an odd number of direct subordinates, or an ordinary employee who has no subordinates. Each employee other than the CEO has exactly one direct supervisor and it's known that the number of the supervisor is always less than the number of the subordinate.

Each ordinary employee votes accoring to their own preference, but each manages votes the same as the majority of their direct subordinates. In the end the chice of fruits are decided by the vote of the CEO (who casts it based on the majority of his direct subordinates).

Antek has an apple garden and he wants apples to win the vote. His friend Borys has a pear garden and he wants pears to win. They agreed to take turns in picking one ordinary employee who neither of them has yet spoken to and persuading him/her to vote for their respective fruits. Both Antek and Borys can always persuasive the employee to vote for their fruits.

Help Antek pick the employees to talk to in order to ensure that apples win the vote. It is known that Antek can always ensure his preferred outcome of the vote.

This is an interactive task. When your program starts, the first line of input contains $N$ ($2 \le N \le 200\,000$), the number of employees in the company.

The second line contains $N - 1$ integers, the numbers of the supervisors of employees $2$ to $N$ ($1 \le A_i < i$, where $A_i$ is the number of the supevisor of employee $i$).

Then your program can send queries to the evaluation stystem.

When your program sends a query of the form "! $X$" ($1 \le X \le N$), this means that Antek should talk to the employee number $X$ next; employee $X$ must be an ordinary employee who neither Antek nor Borys have talked to so far; the evaluation system responds by writing on the next line of input the number $Y$ ($1 \le Y \le N$) of the employee that Borys will talk to next.

When Antek and Borys have talked to all the ordinary employees, your program must terminate. Your solution is graded as correct if your program did not send any invalid queries and Antek perusaded such a subset of employees that the apples win the vote.