33436번 - Mysterious Tree 다국어인터랙티브

문제

This is an interactive problem.

Randias has an unknown hidden tree with $n$ vertices. The tree is either a chain or a star. Randias now needs to determine whether the tree is a chain or a star. He can ask a question in the following form, but no more than $\lceil \frac{n}{2} \rceil + 3$ times:

• Is there an edge between vertex $u$ and vertex $v$ (1ドル \le u, v \le n,ドル $u \neq v$)?

Randias needs to determine which of the two kinds the tree is. Help him to ask the questions and determine the answer.

A tree is called a chain if and only if there exists a permutation $p_{1}, p_{2}, \ldots, p_{n}$ such that, for every $i$ (1ドル \le i < n$), there is an edge $(p_{i}, p_{i + 1})$ in the tree. Here, a permutation of length $n$ is an array where each integer from 1ドル$ to $n$ appears exactly once.

A tree is called a star if and only if there exists a vertex $u$ such that, for every other vertex $v,ドル there is an edge $(u, v)$ in the tree.

In this problem, the interactor is adaptive, which means that the secret tree is not fixed beforehand. Instead, the interactor can change the tree arbitrarily during the interaction. Nevertheless, at every moment, the tree will be consistent with all the answers you got.

입력

Each test contains multiple test cases. The first line contains a single integer $t$ (1ドル \leq t \leq 250$) denoting the number of test cases.

For each test case, the first line contains one integer $n$ (4ドル \le n \le 1000$) denoting the number of vertices. It is guaranteed that the sum of $n$ over all test cases does not exceed 1000ドル$.

출력

제한

인터랙션 프로토콜

You can ask at most $\lceil \frac{n}{2} \rceil + 3$ questions in every test case. To ask a question, output a line of the form "? $u$ $v$" (1ドル \leq u, v \leq n,ドル $u \neq v$). Then you should read the response from standard input.

In response to the query, the interactor will output a line with a single integer: 1ドル$ if there is an edge between $u$ and $v$ in the tree, or 0ドル$ if there is no such edge.

To give your answer, print a line of the form "! 1" if you determined that the tree is a chain, or "! 2" if you determined that it is a star. The output of the answer is not counted towards the limit of $\lceil \frac{n}{2} \rceil + 3$ queries.

After printing the answer, your program should process the next test case, or terminate if there are no more test cases.

After printing each line, do not forget to output end of line and flush the output. To do the latter, you can use fflush(stdout) or cout.flush() in C++, System.out.flush() in Java, or stdout.flush() in Python.

힌트