CF1146C Tree Diameter

有一棵包含 $n$ 个节点和 $n-1$ 条边的带权树。节点编号为 $1$ 到 $n$。每条边的权值为不超过 $100$ 的正整数。定义两个节点之间的距离为它们之间唯一路径上所有边权之和。你需要找到这棵树的直径。直径指的是任意一对节点之间的最大距离。 遗憾的是，树的具体结构并未给出，但你可以对其进行若干次询问。每次询问时，你可以指定两个非空且不相交的节点集合 $p$ 和 $q$，裁判会返回 $p$ 中某个节点与 $q$ 中某个节点之间的最大距离。换句话说，返回 $\max_{x \in p,\, y \in q} dist(x, y)$。在不超过 $9$ 次询问后，你必须报告任意一对节点之间的最大距离。

每个测试点包含若干组测试数据。第一行包含测试数据组数 $t$（$1 \le t \le 1000$）。每组测试数据描述如下。 每组测试数据的第一行包含一个整数 $n$（$2 \leq n \leq 100$），表示树的节点数。 每次询问时，输出一行，格式为 “$k_1\ k_2\ a_1\ a_2\ \ldots\ a_{k_1}\ b_1\ b_2\ \ldots\ b_{k_2}$”，其中 $k_1, k_2 \geq 1$ 且 $k_1 + k_2 \leq n$。这两个集合必须非空且不相交。裁判会返回一个整数，表示 $\max_{p, q} dist(a_p, b_q)$。如果返回 $-1$（说明你的询问无效），请立即退出以避免获得其他判题结果。 每次输出询问后，别忘了输出换行并刷新输出缓冲区，否则会因“Idleness limit exceeded”而被判为超时。具体刷新方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请查阅相关文档 当你准备好输出答案时，输出一行 “$-1\ d$”，其中 $d$ 是所有节点对之间的最大最短距离。 每组测试数据最多只能询问 $9$ 次。 Hack 格式 如需 Hack，请使用如下格式（仅支持单组数据）： 第一行包含一个整数 $t$（$t=1$）。 第二行包含一个整数 $n$（$2 \leq n \leq 100$）。 接下来 $n-1$ 行，每行包含三个整数 $a_i, b_i, c_i$（$1\leq a_i, b_i\leq n$，$1 \leq c_i \leq 100$），表示在 $a_i$ 和 $b_i$ 之间有一条权值为 $c_i$ 的无向边。这些边必须构成一棵树。

见输入格式说明。

在第一个样例中，第一棵树如下图所示： 第一次询问时，$p = \{1\}$，$q = \{2, 3, 4, 5\}$。$p$ 中某个节点与 $q$ 中某个节点之间的最大距离为 $9$（即节点 $1$ 与节点 $5$ 之间的距离）。 第二棵树是一棵有两个节点的树，二者之间有一条权值为 $99$ 的边。 由 ChatGPT 4.1 翻译