CF2258C Far Cities

本题为交互题。 Seferoglu 住在一个叫做 Samsun 的沿海小城，这里很少有人学习竞赛编程。每当有活动举办时，他都需要前往遥远的城市与朋友相聚。由于他已经厌倦了每次精确计算旅途距离，他只想知道最坏情况下他需要穿越的最大距离。你的任务是帮助他找出这个最大距离，并尽量减少他需要查询的次数。 存在一棵有 $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{‡}}$，并给出满足该距离的一对顶点。你最多可以进行 $3 \cdot n$ 次查询。 $^{\text{∗}}$ 一棵树是无环连通图。 $^{\text{†}}$ 树中两点间的距离为唯一简单路径上的边数。 $^{\text{‡}}$ 直径的长度为任意两点间最大距离。

每个测试点包含多个测试用例。第一行为测试用例数 $t$（$1 \le t \le 500$）。之后依次为每组测试用例的数据。 每组测试用例，第一行为 $n$（$2 \le n \le 1000$），表示树的顶点数。 保证所有测试用例的 $n$ 之和不超过 $1000$。

（交互题，不需要标准输出格式描述。）

第一组测试用例的树为 $(1,2), (2,3), (3,4)$。 第二组测试用例的树为 $(1,2)$。 第三组测试用例的树为 $(1,2), (1,3), (1,4)$。 在第三组测试用例中，输出 "! 3 4 2" 也是正确答案。    第一组测试用例的树 第二组测试用例的树 第三组测试用例的树 由 ChatGPT 5 翻译