题目描述

这是一道交互题。

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

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

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

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

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

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

交互方式

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

1. Query(S)

   • 这个函数可以向交互库询问点集 $S$ 所形成的虚树节点个数。
   • 你需要保证 $S$ 非空且 $S$ 中元素互不相同，且值均在 $1∼n$ 之间。交互库会返回点集 $S$ 所形成的虚树节点个数。

2. Report(x, y)

   • 这个函数可以向交互库报告一条你发现的树边。这条边的父节点为 $x$，儿子节点为 $y$。

   • 如果这棵树的形态不可被确定，此时 $x=−1$ 且 $y=−1$。交互库会判断这棵树是否不可确定之后直接退出程序。

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

   • 这个函数没有返回值。

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

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

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

子任务

• 测试包 $1$（$50$ 分）：$2\le N\le 500$， $N$ 为奇数。
• 测试包 $2$（$50$ 分）：$2\le N\le 1000$，$N$ 为偶数或者 $N\gt 500$。

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

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

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

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

1. 你的程序所有的函数调用均合法，且在测试包 1 中，Query 调用的次数不超过$M_1=250000$；在测试包 2 中，Query 调用的次数不超过 $M_2=100000$。

2. 你的程序返回了正确的结果，也就是说：

   1. 如果这棵树不能通过有限次询问确定形态，此时你的程序必须调用恰好一次 Report(x, y) 且 $x=−1,y=−1$。
   2. 如果这棵树可以通过有限次询问确定形态，此时你的程序必须调用恰好 $n−1$ 次 Report(x, y) 且每一次报告了一条不同的正确的树边。

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

• 测试包 $1$： $\Bigg\lfloor \dfrac {50} {\log_2\big (1+ \frac{\max \{4500,x\} } {4500}\big)}\Bigg \rfloor$

• 测试包 $2$： $\Bigg\lfloor \dfrac {50} {\log_2\big (1+ \frac{\max \{10500,x\} } {10500}\big)}\Bigg \rfloor$

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

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

本机测试

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

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

交互操作	注释	返回值
Solve(3)	开始交互过程	无
Query({1,2})	向交互库询问节点集合 $\{1,2\}$ 组成的虚树节点个数	$2$
Query({1,3})	向交互库询问节点集合 $\{1,3\}$ 组成的虚树节点个数
Query({2,3})	向交互库询问节点集合 $\{2,3\}$ 组成的虚树节点个数	$3$
Report(1,2)	向交互库返回树上的一条边 $(1,2)$	无
Report(1,3)	向交互库返回树上的一条边 $(1,3)$

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