4392. 图

【题目背景】

这是一道交互题

【题目描述】

在平面上有 $n$ 个点，第 $i$ 个点的坐标为 $\left(\cos\left(\frac{2i\pi}{n}\right), \sin\left(\frac{2i\pi}{n}\right)\right)$

由题目名称可知，由于这是一道图论题，所以这 $n$ 个点形成了一个无向完全图，每两个点之间都有恰好一条边。比较不同的是，边有两种颜色，黑色和白色。你每次可以询问交互库连接某两点之间边的颜色。

zzq 希望你帮他选出一棵生成树。这棵生成树需要满足，所有边的颜色都相同，并且边两两只在端点处交叉（即组成生成树边的平面上的线段除了共端点以外都不相交）。如果有多个解，你可以任意输出一个。可以证明一定有解。

【交互提示】

选手目录中有 gra.h、sample.cpp 两个文件，以下是详细说明，如果懒得看的话你也可以直接参照 sample.cpp 编写代码。

你需要在你代码的开头 #include "gra.h" 来与交互库交互，不应该实现 main 函数或进行任何文件输入输出，你只需要实现一个函数：void tree(int n)，它接受节点的数量 $n$，并求出一个合法的生成树。

你可以使用交互库提供的函数：bool query(int a, int b)，这个函数接受两个 $[1,n]$ 的不同整数 $a, b$，返回连接 $a$ 和 $b$ 两点的边的颜色，$1$ 表示黑色，$0$ 表示白色。

当你确定了一个合法生成树后，调用恰好 $n−1$ 次函数 void report(int a, int b)，这个函数接受两个 $[1,n]$ 的不同整数 $a,b$，表示你的生成树中的一条边。

样例交互库（下发的 gra.h）会从标准输入输入 $n$ 和一个 $n \times n$ 的关于主对角线对称的 $01$ 矩阵，第 $i$ 行第 $j$ 列的元素表示边 $(i,j)$ 的颜色。

【样例输入】

3
0 1 0
1 0 0
0 0 0

【样例输出】

Good job! You found the following
valid spanning tree in 3 steps.
1 3
3 2

样例输出仅为示例。

【提示】

对于所有数据，$2 \le n \le 1000$。

下表中留空表示无此限制。

交互库是 non-adaptive 的，即在调用你的函数之前每条边的颜色就已经确定了。

你在每个测试点上的得分与你调用 query 函数的次数有关。

如果你的调用次数超过 $\frac{n(n-1)}{2}$，那么你将得到 $0$ 分。

否则，设你的调用次数为 $t$，该测试点满分为 $s$，你将得到 $\left\lfloor\max\left(0.3, \min\left(1, \frac{12\max(n, 5)-t}{10n}\right)\right)s\right\rfloor$ 分。

保证正常交互（即你可能获得分数）时交互库不占用超过 0.5s 时间和 100MB 内存。

【附件下载】