C. Far Cities
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Seferoglu lives in a small coastal city called Samsun, a city where not many people study competitive programming. Whenever an event takes place, he has to travel to far cities where he can meet his friends. Since he is tired of calculating the length of his journey exactly each time, he is just curious about the maximum distance he will ever have to travel between two cities in the worst case scenario. Your task is to help him find this distance while keeping the amount of web searches he has to make small.

There is a hidden tree$$$^{\text{∗}}$$$ with $$$n$$$ vertices. You can make queries. In one query, you choose two vertices $$$1 \le u, v \le n$$$ and an integer $$$0 \le d \le n$$$; the grader responds with $$$1$$$ if $$$\operatorname{dist}(u, v) \ge d$$$ and $$$0$$$ otherwise. Here, $$$\operatorname{dist}(u,v)$$$ denotes the distance$$$^{\text{†}}$$$ between vertices $$$u$$$ and $$$v$$$ in the tree.

Your task is to determine the diameter's length$$$^{\text{‡}}$$$ of the tree and any pair of nodes that are this distance apart. You may ask at most $$$3 \cdot n$$$ queries.

$$$^{\text{∗}}$$$A tree is a connected graph without cycles.

$$$^{\text{†}}$$$The distance between two nodes in a tree is the number of edges in the unique simple path between these nodes.

$$$^{\text{‡}}$$$The diameter's length is the largest distance between two vertices.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains $$$n$$$ ($$$2 \le n \le 1000$$$), denoting the number of vertices in the tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Interaction

To make a query, first pick $$$u$$$, $$$v$$$ and $$$d$$$ ($$$1 \le u, v \le n$$$, $$$0 \le d \le n$$$), a pair of nodes and a constant to check the distance between them against, and output the following line (without quotes):

  • "? u v d"

Afterwards, you should read one single integer ($$$1$$$ or $$$0$$$), whether $$$d$$$ was less than or equal to $$$\text{dist}(u, v)$$$ or not.

Note you may ask at most $$$3 \cdot n$$$ such queries.

Next, if your program has found an answer, it should print the following line (without quotes):

  • "! u v d"

For some candidate $$$u$$$ and $$$v$$$ nodes denoting the endpoints of a diameter ($$$1 \le u, v \le n$$$) and the length of the path between them ($$$0 \le d \le n-1$$$). If there are multiple answers, any one of them may be printed.

Note that this action is not counted towards the maximum query limit.

The grader is non-adaptive. This means that the graph is fixed at the beginning and will not change based on your interactions.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

Hacks

To hack, use the following format:

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$).

The first line of each test case contains $$$n$$$ ($$$2 \le n \le 1000$$$), denoting the number of vertices in the tree.

The next $$$n-1$$$ lines of each test case contain two integers each $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$), denoting the edges of the tree.

$$$^{\text{∗}}$$$To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
3

4

1

0

0

0

2

4

1

1

1

1

0

0

0

0
Output
? 1 2 1

? 1 2 2

? 2 3 2

? 3 4 2

! 1 4 3

! 1 2 1

? 1 2 1

? 1 3 1

? 1 4 1

? 3 4 2

? 3 4 3

? 1 2 2

? 1 3 2

? 1 4 2

! 4 2 2
Note

The hidden graph in the first test case is $$$(1,2), (2,3), (3,4)$$$.

The hidden graph in the second test case is $$$(1,2)$$$.

The hidden graph in the third test case is $$$(1,2), (1,3), (1,4)$$$.

In the third test case, the answer "! 3 4 2" is also correct.

The tree of the first testcaseThe tree of the second testcaseThe tree of the third testcase