CF1370F2.The Hidden Pair (Hard Version)

Note that the only difference between the easy and hard version is the constraint on the number of queries. You can make hacks only if all versions of the problem are solved.

This is an interactive problem.

You are given a tree consisting of $n$ nodes numbered with integers from $1$ to $n$. Ayush and Ashish chose two secret distinct nodes in the tree. You need to find out both the nodes. You can make the following query:

• Provide a list of nodes and you will receive a node from that list whose sum of distances to both the hidden nodes is minimal (if there are multiple such nodes in the list, you will receive any one of them). You will also get the sum of distances of that node to the hidden nodes.

Recall that a tree is a connected graph without cycles. The distance between two nodes is defined as the number of edges in the simple path between them.

More formally, let's define two hidden nodes as $s$ and $f$. In one query you can provide the set of nodes ${a_1, a_2, \ldots, a_c}$ of the tree. As a result, you will get two numbers $a_i$ and $dist(a_i, s) + dist(a_i, f)$. The node $a_i$ is any node from the provided set, for which the number $dist(a_i, s) + dist(a_i, f)$ is minimal.

You can ask no more than $11$ queries.

注意：简单版本与困难版本的唯一区别在于查询次数的限制。仅当该题的所有版本均被解决时，才允许进行 Hack。

这是一道交互式题目。

你将得到一棵由 $n$ 个节点构成的树，节点编号为 $1$ 到 $n$ 的整数。Ayush 和 Ashish 在树中选定两个互不相同的秘密节点。你需要找出这两个节点。你可以执行如下查询：

• 提供一个节点列表，系统将返回该列表中到两个隐藏节点的距离之和最小的一个节点（若列表中存在多个满足条件的节点，则返回其中任意一个）。同时，你还将获得该节点到两个隐藏节点的距离之和。

回忆一下：树是一种无环连通图。两个节点之间的距离定义为它们之间简单路径上的边数。

更形式化地，设两个隐藏节点为 $s$ 和 $f$。在一次查询中，你可以提供树中的一组节点 $\{a_1, a_2, \ldots, a_c\}$。作为响应，你将收到两个数：$a_i$ 和 $dist(a_i, s) + dist(a_i, f)$。其中 $a_i$ 是所提供集合中使 $dist(a_i, s) + dist(a_i, f)$ 最小的任意一个节点。

你最多可以进行 $11$ 次查询。

The first line contains a single integer $t$ $(1 \leq t \leq 10)$ — the number of test cases. Please note, how the interaction process is organized.

The first line of each test case consists of a single integer $n$ $(2 \le n \le 1000)$ — the number of nodes in the tree.

The next $n - 1$ lines consist of two integers $u$, $v$ $(1 \le u, v \le n, u \ne v)$ — the edges of the tree.

第一行包含一个整数 $t$（$1 \leq t \leq 10$）——测试用例的数量。请注意交互过程的组织方式。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 1000$）——树中节点的数量。

接下来的 $n - 1$ 行每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n,\ u \ne v$）——树的边。

The tree from the first test is shown below, and the hidden nodes are $1$ and $3$.

第一个测试用例中的树如下图所示，隐藏的节点为 $1$ 和 $3$。