406333: GYM102365 C Unjob Search

Aram got bored of having a job, so he quit and went off to the distant country of Lalaland.

Lalaland has $$$N$$$ cities with unexciting names of $$$1, 2,\ldots, N$$$. There are $$$N-1$$$ rail lines connecting pairs of cities, making it possible to get from any city to any other. In other words, Lalaland is a tree.

Lalaland has something called an unjob. Unjobs are similar to jobs, except that people who have an unjob can't be fired, have no obligations, and don't get paid. This is exactly what Aram is looking for so he can prove theorems all day long.

The Lalaland government knows that the general public views these unjobs as somewhat unsavory, and they may also be attracting large numbers of foreigners into the country. Hence they passed a law requiring people with unjobs to live in faraway terminal cities: cities that are only connected to one rail line. The government hoped that this would keep people with unjobs far away from the center of their country.

Aram wants to go to a terminal city. Having never been to Lalaland, he asked his cosmopolitan friend David if he knows of a terminal city. David said no, but claimed to have travelled between every pair of cities of Lalaland and can remember if any given city was on the unique shortest sequence of rail lines between them. He lets Aram ask up to $$$N$$$ questions of the following form:

"For cities $$$a$$$, $$$b$$$, and $$$c$$$, do you pass by city $$$b$$$ as you travel along the shortest path from $$$a$$$ to $$$c$$$?"

If Aram asks more than $$$N$$$ questions, David will get tired and take a nap for who knows how long. Help Aram quickly find a terminal city!

The first line of input from the judge contains a single integer $$$N$$$ ($$$3\le N \le 2\,000$$$), the number of cities in Lalaland.

Following this, you may submit up to $$$N$$$ queries of the following forms:

• ? a b c — ($$$1\le a, b, c \le N$$$) which asks if city $$$b$$$ will be visited while taking the shortest set of rail lines from city $$$a$$$ to city $$$c$$$.

The judge will respond with either $$$1$$$ indicating that city $$$b$$$ is indeed between cities $$$a$$$ and $$$c$$$, or $$$0$$$ indicating that it is not.

At any time, you may submit an answer in the following form:

• ! x ($$$1\le x \le N$$$) — which means your program claims that $$$x$$$ is a terminal city.

After answering, your program must terminate immediately to get a verdict. Failing to follow this interaction protocol may result in unexpected errors.

If your input is malformed, the judge will output -1. Upon reading -1 your program should exit immediately to get a wrong answer verdict, otherwise you may get another error.

Please be sure to use the stream flushing operation after each query in order not to leave part of your output in the buffer. For example, in C++ you can use fflush(stdout) or end with cout <{}< endl or cout <{}< flush. In Java you can use System.out.flush(). In Python, you can use stdout.flush().

3

0

1

 
? 1 3 2

? 3 2 1

! 1

The sample has two terminal cities, $$$1$$$ and $$$3$$$. Either answer would be accepted.