CF2258C.Far Cities

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.

这是一个交互式问题。

塞费罗格鲁住在一座名为萨姆松的小型沿海城市，这座城市里很少有人学习竞赛编程。每当有活动举办时，他都不得不前往遥远的城市与朋友们会面。由于他厌倦了每次都要精确计算自己旅途的长度，他只是好奇：在最坏情况下，他需要在两座城市之间旅行的最大距离是多少？你的任务是在尽可能减少他所需进行的网络搜索次数的前提下，帮助他找出这一距离。

存在一棵隐藏的、具有 $n$ 个顶点的树$^{\text{∗}}$。你可以提出查询。每次查询中，你需选择两个顶点 $1 \le u, v \le n$ 和一个整数 $0 \le d \le n$；评测程序将返回 $1$，当且仅当 $\operatorname{dist}(u, v) \ge d$，否则返回 $0$。其中，$\operatorname{dist}(u,v)$ 表示树中顶点 $u$ 与 $v$ 之间的距离$^{\text{†}}$。

你的任务是确定该树的直径长度$^{\text{‡}}$，以及任意一对相距该长度的节点。你最多可进行 $3 \cdot n$ 次查询。

$^{\text{∗}}$ 树是一类无环的连通图。

$^{\text{†}}$ 树中两个节点之间的距离定义为连接这两个节点的唯一简单路径所含边的数量。

$^{\text{‡}}$ 直径长度即所有顶点对之间距离的最大值。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是各测试用例的描述。

每个测试用例的第一行包含 $n$（$2 \le n \le 1000$），表示树中顶点的数量。

保证所有测试用例的 $n$ 值之和不超过 $1000$。

null

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 testcase

The tree of the second testcase

The tree of the third testcase

第一个测试用例中的隐藏图是 $(1,2), (2,3), (3,4)$。

第二个测试用例中的隐藏图是 $(1,2)$。

第三个测试用例中的隐藏图是 $(1,2), (1,3), (1,4)$。

在第三个测试用例中，答案 "! 3 4 2" 同样正确。

第一个测试用例对应的树

第二个测试用例对应的树

第三个测试用例对应的树