这是一道交互题。

出题人有一棵大小为 $N$ 的有根二叉树（每个点只有不超过两个儿子）。节点的编号为 $1 \sim N$。

注意你并不知道这一棵树的根节点，也不知道这一棵树的具体形态。你只知道树上的节点个数 $N$。

定义树上一个点集 $S$ 的虚树点集 $V = \{\operatorname{LCA} (u, v) \mid u,v \in S \}$，其中 $\operatorname{LCA}(x, y)$ 表示 $x, y$ 在树上的最近公共祖先（这里我们定义 $\operatorname LCA(x, x) = x$）。

你想要知道这一棵树的结构，于是慷慨的出题人给了你一个交互库。这个交互库会回答你的若干次询问，每次询问你可以给定一些点的标号(不能重复)，交互库会返回这些点构成点集的虚树点集的大小。

交互库的询问次数是有限的，你需要在有限的询问中确定这一棵树的形态。当然，有可能出题人只讲 6-1，那一棵二叉树无法通过任意的有限次询问问出树的结构。这个时候你需 要向交互库说明不可能通过这种询问方式确定树的形态。

请不要试图攻击交互库，否则你的得分会被手动修改为 $0$ 分。

交互方式

你不需要，也不应该实现主函数，你只需要实现函数 Solve(N)，并且请包含一个头文件 tree.h。这里的 $N$ 表示这一棵树的节点个数。你可以通过调用下面两个函数与交互库进行交互：

1. Query(S)
   • 这个函数可以向交互库询问点集 $S$ 所形成的虚树节点个数。
   • 你需要保证 $S$ 中元素互不相同，且值均在 $1 \sim n$之间。交互库会返回点集 $S$ 所形成的虚树节点个数。
2. Report(x, y)
   • 这个函数可以向交互库报告一条你发现的树边。这条边的父节点为 $x$，儿子节点为 $y$。
   • 如果这棵树的形态不可被确定，此时 $x = -1$ 且 $y = -1$。交互库会判断这棵树是否不可确定之后直接退出程序。

你需要保证报告发现所有树边均合法，且每一次报告的树边互不相同。

这个函数没有返回值。

评测时，交互库会恰好调用solve 一次。

本题保证所使用的图在交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定的，你不需要关心这些操作在交互库中的具体实现。

数据保证在调用次数限制下，交互库运行所需的时间不超过 1.5s；交互库使用的内存大小固定，且不超过 128 MB。

子任务

• 测试包1（50分）：$2 \leq N \leq 500$， $N$ 为奇数。
• 测试包2（50分）：$2 \leq N \leq 1\,000$，$N$ 为偶数或者 $N ＞500$。

对于测试包 1，额外满足出题人给定的树上的每一个节点恰好有 $0$ 或者 $2$ 个儿子节点。

注意，选手可以通过给定的 $N$ 的奇偶性和 $N$ 的大小判断其属于哪一个测试点。

本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

基于条件基础，在一个测试点中，你的程序被判定为正确的程序，当且仅当：

1. 你的程序所有的函数调用均合法，且在测试包 $1$ 中，Query 调用的次数不超过 $M_1 = 250\, 000$；在测试包 $2$ 中，Query 调用的次数不超过 $M_2=100\,000$。
2. 你的程序返回了正确的结果，也就是说：
   1. 如果这棵树不能通过有限次询问确定形态，此时你的程序必须调用恰好一次 Report(x, y) 且 $x = -1, y = -1$。
   2. 如果这棵树可以通过有限次询问确定形态，此时你的程序必须调用恰好 $n-1$ 次 Report(x, y) 且每一次报告了一条不同的正确的树边。

如果选手程序被判定不是正确的，则该测试点选手得到 $0$ 分，否则交互库将会根据选手程序的交互次数给分。假设选手的程序调用了 $x$ 次 Query 操作，对于测试包 1、2，选手的得分分别为：

测试包 $1$：$\displaystyle\left\lfloor \frac{50}{\log_2 \left(1 + \frac{\max\{4500, x\}}{4500}\right)} \right\rfloor$

测试包 $2$：$\displaystyle\left\lfloor \frac{50}{\log_2 \left(1 + \frac{\max\{10500, x\}}{10500}\right)} \right\rfloor$

一个测试包的得分为这个测试包内所有测试点的得分的最低值，而选手在本题的得分为两个测试包得分之和。

数据保证总存在一种交互方式，使得其能够在 $M = \min\{M_1, M_2\} = 100\,000$ 次询问内唯一确定树的形态，或者确定在有限次内无法判断这一棵树的形态。同时保证存在一个标准算法，使得对于两个测试包其都可以获得 $50$ 分的分数。

本机测试

在附加文件（下载）中给出了 tree.cpp，这是本题的一个参考实现，选手可以在这一份代码的基础上编写自己的代码，也可以自己重新编写一份。下发的这一份代码不保证可以通过所有的测试点。 假设选手程序为 tree.cpp,使用命令 g++ -static tree.cpp grader.cpp -o tree -O2 -std=c++11 即可得到可执行文件 tree。

可执行文件将从标准输入读入以下格式的数据：

1. 第一行两个整数 $N, M$，表示树的大小和限制询问次数。
2. 第 $2$ 到 $N+1$ 行每行两个整数，第 $i$ 行表示标号为在 $i-1$ 的点的两个儿子。如果儿子个数小于两个，缺失的部分用 $0$ 代替。
3. 最后一行一个整数 $0$ 或 $1$,表示是否有唯一解（无为 $0$，有为 $1$）

读人完成之后，交互库将调用恰好一次函数 Solve(N),并且用输入的数据测试你的函数。你的函数正确返回后，交互库会判断你的计算是否正确,若正确则会输出 OK, Accepted! 和交互函数调用次数相关信息，否则会输出相应的错误信息。

样例

一个可能的样例输入数据为：

3 250000
2 3
0 0
0 0
1

在这个数据中一个可能的正确的过程如下：

这个交互过程总共调用了 $3$ 次 Query，并且返回了正确的答案。