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

# | Points | Constraints |
---|---|---|

1 | 7 | $n \leq 9$ |

2 | 10 | $n \leq 30$ |

3 | 83 | $n \leq 500$ |

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