Where Is the Root?

Task

You are given a tree of $n$ vertices. The tree is a graph such that there is exactly one simple path between every pair of vertices. It's also guaranteed that at least one vertex is directly connected by an edge to at least $3$ vertices. One of the vertices is the root, and your task is to find it. In order to do this, you are allowed to ask queries of the following form:

• For a given set $a_1, a_2,\dots, a_m$ of vertices, check if their lowest common ancestor is in this set.

A vertex $v$ is a common ancestor of a set $S$ of vertices if the paths from all vertices in $S$ to the root pass through $v$. The lowest common ancestor (LCA) of a set $S$ of vertices is the common ancestor of $S$ which is farthest from the root.

Interaction protocol

You must implement one function:

void solve(int n, vector<pair<int,int>> V);

You can call the following functions:

bool query(vector<int> a);
void check(int u);

The function solve will be called exactly once at the beginning of the interaction with two parameters:

• $n$: the number of nodes
• $V$: the edges of the given tree.

The function query may be called by the contestant no more than $1\ 000$ times. It will return a boolean value true if the LCA (Lowest Common Ancestor) of the nodes is in the given set, and false otherwise.
To check if a node is the root, you can call the check function. After that, the interaction will terminate, and you can't ask any more queries or check for other nodes.
Atention! You must not implement the main function, and must #include the root.h header! You can use global variables and other functions.

Constraints and clarifications

• In the first and second subtask you can ask at most $1\ 000$ queries.
• In the third subtask, let $k$ be the maximum number of queries you asked in any test. If $k \leq 9$, you will receive all the points for this subtask ($83$ points). Otherwise, you will get $\displaystyle \lfloor \max(10, 83 \cdot (1- \frac{\ln(k-6)}{7})) \rfloor$ points.

Example

• Grader runs solve(7, {{4,1},{1,2},{4,3},{3,5},{3,6},{4,7}});.
• User calls query({2, 5, 6}); and grader returns false.
• User calls query({3, 6, 3, 5}); and grader returns true.
• User calls query({2, 1, 7}); and grader returns false.
• User calls query({2, 4, 6}); and grader returns true.
• User calls check(4); and the program ends successfully.

Explanation

The hidden root is vertex $4$.
In the first query, the LCA of vertices $5$ and $6$ is vertex $3$ which is not among vertices $5$ and $6$ so the answer is false.
In the second query, the LCA of vertices $3$, $5$, and $6$ is vertex $3$ so the answer is true.
In the third query, the LCA of vertices $1$ and $7$ is vertex $4$ so the answer is false.
In the fourth query, the LCA of vertices $4$ and $6$ is vertex $4$ so the answer is true.
After that, we can guess that root is vertex $4$ which is the correct answer.