This is an interactive problem.

The problem setter has a rooted binary tree of size $N$ (each node has at most two children). The nodes are labeled $1 \sim N$.

Note that you do not know the root of the tree, nor do you know the specific structure of the tree. You only know the number of nodes $N$ in the tree.

Define the virtual tree node set $V$ of a set of nodes $S$ as $V = \{\operatorname{LCA}(u, v) \mid u, v \in S\}$, where $\operatorname{LCA}(x, y)$ denotes the lowest common ancestor of $x$ and $y$ in the tree (we define $\operatorname{LCA}(x, x) = x$).

You want to determine the structure of this tree, so the generous problem setter has provided an interactive library. This library will answer several queries for you. In each query, you can provide a set of node labels (no duplicates), and the library will return the size of the virtual tree node set formed by these nodes.

The number of queries allowed is limited, and you must determine the structure of the tree within this limit. Of course, it is possible that the problem setter has provided a tree that cannot be uniquely determined by any finite number of queries. In this case, you need to inform the interactive library that it is impossible to determine the tree structure using this method.

Please do not attempt to attack the interactive library; otherwise, your score will be manually set to $0$.

Interaction

You do not need to, and should not, implement the main function. You only need to implement the function Solve(N) and include the header file tree.h. Here, $N$ represents the number of nodes in the tree. You can interact with the library by calling the following two functions:

1. Query(S)
   • This function queries the library for the number of nodes in the virtual tree formed by the set $S$.
   • You must ensure that the elements in $S$ are distinct and that their values are between $1$ and $N$. The library will return the size of the virtual tree node set formed by $S$.
2. Report(x, y)
   • This function reports a tree edge you have discovered. The parent node of this edge is $x$, and the child node is $y$.
   • If the tree structure cannot be determined, set $x = -1$ and $y = -1$. The library will determine if the tree is indeed indeterminable and then terminate the program.

You must ensure that all reported tree edges are valid and that each reported edge is unique.

This function has no return value.

During evaluation, the interactive library will call Solve exactly once.

The problem guarantees that the graph used is fully determined before the interaction begins and is not constructed dynamically based on your program's actions. Therefore, the interactive operations are deterministic, and you do not need to worry about the specific implementation of these operations within the library.

The data guarantees that the time required for the library to run within the query limit does not exceed $1.5$ seconds; the memory used by the library is fixed and does not exceed $128$ MB.

Subtasks

• Test Package 1 (50 points): $2 \leq N \leq 500$, $N$ is odd.
• Test Package 2 (50 points): $2 \leq N \leq 1\,000$, $N$ is even or $N > 500$.

For Test Package 1, it is additionally guaranteed that every node in the given tree has exactly $0$ or $2$ children.

Note that participants can determine which test package a test case belongs to based on the parity and size of $N$.

This problem is subject to the same restrictions as traditional problems. For example, compilation errors will result in $0$ points for the entire problem, while runtime errors, time limit exceeded, or memory limit exceeded will result in $0$ points for the corresponding test cases. You may only access variables you have defined and those provided by the interactive library; attempting to access other memory spaces may result in compilation or runtime errors.

Based on the conditions, your program is judged as correct for a test case if and only if:

1. All function calls made by your program are valid, and in Test Package 1, the number of Query calls does not exceed $M_1 = 250\,000$; in Test Package 2, the number of Query calls does not exceed $M_2 = 100\,000$.
2. Your program returns the correct result, meaning:
   1. If the tree cannot be determined by a finite number of queries, your program must call Report(x, y) exactly once with $x = -1, y = -1$.
   2. If the tree can be determined by a finite number of queries, your program must call Report(x, y) exactly $n-1$ times, with each call reporting a different, correct tree edge.

If the participant's program is judged as incorrect, the test case receives $0$ points. Otherwise, the library will award points based on the number of interactions. Assuming the program performs $x$ Query operations, the scores for Test Packages 1 and 2 are:

Test Package 1: $\displaystyle\left\lfloor \frac{50}{\log_2 \left(1 + \frac{\max\{4500, x\}}{4500}\right)} \right\rfloor$

Test Package 2: $\displaystyle\left\lfloor \frac{50}{\log_2 \left(1 + \frac{\max\{10500, x\}}{10500}\right)} \right\rfloor$

The score for a test package is the minimum score among all test cases within that package, and the participant's total score is the sum of the scores of the two test packages.

The data guarantees that there always exists an interaction strategy that can uniquely determine the tree structure within $M = \min\{M_1, M_2\} = 100\,000$ queries, or determine that the tree structure cannot be determined in a finite number of steps. It is also guaranteed that a standard algorithm exists that can achieve $50$ points for both test packages.

Local Testing

The provided tree.cpp in the additional files is a reference implementation. You may write your code based on this file or write your own from scratch. The provided code is not guaranteed to pass all test cases. Assuming your program is tree.cpp, use the command g++ -static tree.cpp grader.cpp -o tree -O2 -std=c++11 to generate the executable tree.

The executable will read data from standard input in the following format:

1. The first line contains two integers $N, M$, representing the tree size and the query limit.
2. The next $N$ lines each contain two integers. The $i$-th line represents the two children of the node labeled $i-1$. If there are fewer than two children, use $0$ for the missing ones.
3. The last line contains an integer $0$ or $1$, indicating whether there is a unique solution ($0$ for no, $1$ for yes).

After reading the input, the library will call Solve(N) exactly once and test your function with the provided data. After your function returns correctly, the library will verify your calculations. If correct, it will output OK, Accepted! along with information about the number of interaction calls; otherwise, it will output the corresponding error message.

Examples

A possible sample input is:

3 250000
2 3
0 0
0 0
1

A possible correct process for this data is:

This interaction process called Query a total of $3$ times and returned the correct answer.