This is an interactive problem.

Given a tree $T$, we define the minimal connected subgraph of a set of vertices $S$ in the tree as the smallest connected subgraph (subtree) that contains all vertices in $S$.

Given the size $n$ of the tree, you can perform several queries. In each query, you provide a set of vertices $S$ and a vertex $x$ in the tree. The interactor will return a boolean value indicating whether $x$ is in the minimal connected subgraph of $S$. You need to determine the structure of the tree.

Implementation Details

Your program must include C.hpp.

You need to implement the following function:

std::vector<std::pair<int, int> > work(int n)

Here, $n$ is the size of the tree as described in the problem.

The std::vector<std::pair<int, int> > you return should contain $n-1$ pairs, each representing the two endpoints of an edge in the tree. You must ensure that the returned vector forms a valid tree; otherwise, your program will receive $0$ points.

You can interact with the interactor by calling the following function:

bool ask(std::vector<int> S, int x)

Here, $S$ is the set of vertices you provide, and $x$ is the vertex you provide. You must ensure that $S$ is not empty, and all vertices in $S$ and $x$ are in the range $[1, n]$; otherwise, your program will receive $0$ points. The function returns true if $x$ is in the minimal connected subgraph of $S$, and false otherwise.

For further details, please refer to the provided sample code.

Please note: The time complexity of the interaction function is $O(|S|)$. You may receive a Time Limit Exceeded error if the set $S$ you provide is too large.

Testing Your Program

The sample grader will read input in the following format:

The first line contains a positive integer $n$, representing the size of the tree. The next $n-1$ lines each contain two integers $x, y$, representing the two endpoints of an edge. Vertex indices are 1-based.

The sample grader will return your error message or the following result:

Your answer is correct.You made AAA queries with total size BBB.

Where AAA is the number of queries you made, and BBB is the total size of the sets $S$ you provided in your queries.

Examples

Input 1

5
1 2
1 3
2 4
2 5

Output 1

Your answer is correct.You made 0 queries with total size 0.

Subtasks

This problem consists of a single test package containing several test cases.

For each test case, if your program makes an invalid query or returns an incorrect tree structure, you will receive $0$ points for that test case. Otherwise, let $step$ be the number of queries your program makes. Your score for that test case will be $\min(\lfloor \frac{2.2\times 10^6}{step} \rfloor, 100)$.

Your final score for this problem will be the minimum of the scores obtained across all test cases.

For all test cases, $n=1000$.