After hearing some nasty rumours about him, Mike is determined to find the source of the rumour! There are suspects labelled from to who have been involved in gossiping, with suspect being the creator of the rumour. Between these suspects, there are friendships. The -th friendship indicates that suspects and are friends with each other. Although Mike does not know the value of , he is aware of all friendships.
The rumour spreads according to the following procedure:
- On day , suspect will create the rumour.
- On day , suspect will tell the rumour to all of their friends.
- Then, on day , the suspects who heard the rumour for the first time on day will tell the rumour to all of their friends who have not yet heard the rumour.
Josh knows who started the rumour, but he is too scared to directly tell Mike, lest he feel the wrath of suspect . However, he will be willing to answer up to queries. In each query, Mike chooses an integer and accuses suspect of starting the rumour. If , then Josh will tell Mike that he has found the source of the gossip. Otherwise, Josh will tell Mike an integer such that suspect was first aware of the rumour on a strictly earlier day than when suspect was first aware of the rumour. If there are multiple possible values of , then Josh can tell Mike any of them. Recall that suspect was first aware of the rumour on day .
Can you help Mike determine who started the rumour?
Constraints
It is guaranteed that all suspects will eventually be aware of the rumour.
Subtask 1 [10%]
For , and .
Subtask 2 [10%]
For , and .
Subtask 3 [80%]
No additional constraints.
Note that all previous subtasks must be passed for this subtask to be evaluated.
Interaction
This is an interactive problem, where you will play the role of Mike and the interactor will play the role of Josh. Note that the interactor is adaptive.
First, you should read in the value of on a single line, representing the number of suspects.
Then, on the -th of the following lines, you should read in two space-separated integers and , representing the -th friendship.
Then, you should begin making queries. To make a query, output an integer on a single line, indicating that you will accuse suspect of starting the rumour. You should then read in an integer on the following line. If , then will be , and you should terminate your program to receive an Accepted verdict. Otherwise, indicates that suspect was first aware of the rumour on a strictly earlier day than when suspect was first aware of the rumour.
If at any point you make an invalid query, or make more than queries, the interactor will respond with -1
on the following line. Upon reading this value, you should terminate your program to receive a Wrong Answer verdict. Otherwise, you may receive an arbitrary verdict.
Please note that you may need to flush stdout
after each operation, or interaction may halt. In C++, this can be done with fflush(stdout)
or cout << flush
(depending on whether you use printf
or cout
). In Java, this can be done with System.out.flush()
. In Python, you can use sys.stdout.flush()
.
Sample Interaction
>>>
denotes your output. Do not print this out.
5
1 2
2 3
2 4
1 5
>>> 5
3
>>> 2
4
>>> 4
0
Explanation
In the image above, a line drawn between two suspects indicates a friendship.
In this example, . Note that:
- Suspect was first aware of the rumour on day .
- Suspect was first aware of the rumour on day .
- Suspects and were first aware of the rumour on day .
- Suspect was first aware of the rumour on day .
First, Mike guesses that suspect started the rumour. Josh responds by telling Mike that suspect was aware of the rumour before suspect .
Then, Mike guesses that suspect started the rumour. Josh responds by telling Mike that suspect was aware of the rumour before suspect .
Finally, Mike guesses that suspect started the rumour. Since Mike guessed correctly, Josh responds with .
As Mike has successfully guessed the suspect in no more than queries, you would receive an Accepted verdict for this test case.
Comments