题目描述

译自 CEOI2016 Day1 T1「ICC」

最近宇航员 Astro 开始在国际空间站（ISS）实习了。他的首份差事，是研究 Mar Sara 星球上的人族文明。人族已经建造了以 $1,\dots,N$ 编号的 $N$ 座城市，但出于经费考虑，他们尚未建造往来于城市间的道路。

不巧的是，人族恰巧在 Astro 开始实习的同时开始了建造道路。人族想尽快地连接所有城市，所以他们不会傻傻地在已经连通的两座城市间再度浪费时间。当每次人族建造道路时，Astro 都想知道在下一条道路建造之前这条道路连接了哪些城市。

幸运地，Astro 能够使用伟大的发明 SETI，这是一种可以看到 Mar Sara 上已有道路的卫星。只需给定两个不相交的城市编号集合，SETI 就能判断是否至少有一条道路直接将第一个集合中的一个点和第二个集合中的另一个点连通。

交互流程

1. 人族建造了一条道路。
2. Astro 试图使用 SETI 以发现新建的道路。
3. 他将结果发送给国际空间站科学委员会。
4. 如果已有的道路少于 $N - 1$ 条，回到第一步。

你的任务是帮助 Astro 完成这份工作。

---

交互方式

你需要实现一个仅会在交互程序开头被调用一次的函数 run()。你需要在这个函数中调用 query() 以使用 SETI，以及调用 setRoad() 以提交你的判断结果。你可以在调用 setRoad() 之前调用多次 query()。

---

交互函数说明

函数 query()

C/C++:

int query(int size_a, int size_b, int a[], int b[]);

Pascal:

function query(size_a, size_b : longint; a, b : array of longint) : longint;

功能说明：

• 调用此函数以建立与 SETI 之间的联系
• 参数 size_a 和 size_b 表示两个集合的大小
• 数组 a[] 和 b[] 表示两个集合中的城市编号
• 注意：这两个集合必须是不相交的
• 返回值：如果存在一条边连接两个集合中的城市，返回 1，否则返回 0

---

函数 setRoad()

C/C++:

void setRoad(int a, int b);

Pascal:

procedure setRoad(a : longint, b : longint);

功能说明：

• 调用此过程以告诉科学委员会你发现最新建成的道路连接 $a$ 和 $b$
• 如果判断错误，这个测试点计 0 分
• 如果调用 $N - 1$ 次，程序终止
• 否则，人族就会新建一条道路，并且你需要继续你的工作
• 在某一次调用此过程之后调用的任意 query() 都将考虑新道路的影响

---

需要实现的过程 run()

C/C++:

void run(int N);

Pascal:

procedure run(N : longint);

功能说明：

• 你提交的程序必须实现此过程，且必须于此调用 query() 和 setRoad()
• 接受的参数 $N$ 表示人族的城市数量
• 如果此过程在调用 $N - 1$ 次 setRoad() 前终止，该测试数据计 0 分

---

实现提示

C/C++

你必须在程序中写入：

#include "icc.h"

Pascal

你必须定义 unit icc，同时你需要声明 uses graderhelplib 以保证交互器正常运作。

---

标准输入输出交互方法

在 LibreOJ 上，本题只实现了使用 C/C++ 语言进行函数交互的功能。如果希望使用其他语言，请使用标准输入输出与交互器交互。

交互格式

1. 初始化：你的程序应从标准输入中读入一个整数 $N$，表示 void run(int N) 中的参数 $N$。

2. 调用 query()：

   • 输出格式：? size_a size_b a[0] a[1] ... a[size_a-1] b[0] b[1] ... b[size_b-1]
   • 输出后，你的程序应该清理缓冲区
   • 然后从标准输入中读入一个整数，表示调用函数的返回值

3. 调用 setRoad()：

   • 输出格式：! a b
   • 输出后，你的程序应该清理缓冲区

4. 结束：在 run() 函数结束后，你的程序应输出一行 F，表示你的程序已经结束。

---

评分标准

本题共分为 6 组测试数据。

倘若你对于同一组数据都在调用不多于 $M$ 次 query() 的前提下完美地猜对了所有道路，你才能得到这一组数据的分数。

各测试点 $N, M$ 的值与分数如下表所示：

测试数据编号	$N =$	$M =$	分数
1	15	1500	7
2	50	2500	11
3	100	2250	22
4		2000	21
5		1775	29
6		1625	10

---

样例交互过程

下表展示了一个 $N = 4$ 的交互样例：

选手行为	交互器行为	注释
-	run(4)	交互器以 $N=4$ 开始。第一条道路修建在城市 2 和 4 之间，选手是不知道的
query(1, 3, {1}, {2, 3, 4})	return 0	查询集合 $\{1\}$ 和 $\{2,3,4\}$。答案是 false：因为没有从 1 出发到达任何城市的道路
query(1, 2, {2}, {3, 4})	return 1	查询集合 $\{2\}$ 和 $\{3,4\}$。答案是 true：有一条从 2 到 4 的道路
query(1, 1, {2}, {3})	return 0	查询 2 和 3 之间是否有边
setRoad(2, 4)	-	选手回答有一条道路 $(2,4)$，这是正确的。交互器会在 1 和 3 之间生成一条新路
query(2, 2, {2, 4}, {1, 3})	return 0	查询集合 $\{2,4\}$ 和 $\{1,3\}$。答案是 false
setRoad(1, 3)	-	选手回答有一条道路 $(1,3)$，这是正确的。交互器会在 1 和 4 之间生成一条新路
query(2, 2, {2, 4}, {1, 3})	return 1	和之前的查询是一样的，但现在答案为 true，因为新建了一条道路
query(1, 2, {2}, {1, 3})	return 0	查询 2 与 1,3 之间是否有边
query(1, 1, {4}, {3})		查询 4 和 3 之间是否有边
setRoad(4, 1)	exit	选手最后一条道路 $(4,1)$ 回答正确。交互器接收最后一次猜测，并给这个测试点的满分

---

样例解释

在这个样例中，交互器依次建造了以下道路：

1. $(2, 4)$
2. $(1, 3)$
3. $(1, 4)$

选手通过多次二分查询成功找到了所有道路。