宇航员 Astro 刚刚在国际空间站 (ISS) 开始了他的实习。他的工作是研究来自 Mar Sara 星球的 Terran 文明。Terran 人已经建造了 $N$ 座城市，编号从 $1$ 到 $N$，但他们之间还没有建造任何道路。
就在 Astro 开始实习时，Terran 人开始在 Mar Sara 上建造道路。众所周知，Terran 人希望尽快连接这些城市，因此他们不会在已经通过一条或多条道路连接的 2 座城市之间建造道路。每当 Terran 人建造一条新道路时，Astro 都想在下一条道路建成之前知道它连接了哪些城市。
幸运的是，Astro 可以使用 SETI Masterpieces，这是一种可以观察 Mar Sara 并查看已建成道路的新型卫星。给定两组不相交的城市，SETI 能够判断是否存在至少一条直接连接第一组中的某座城市与第二组中的某座城市的道路。
交互过程如下：
- Terran 人建造一条道路。
- Astro 使用 SETI 尝试发现刚建成的道路。
- 他前往 ISS 科学委员会，向他们展示他关于刚创建道路的答案。
- 如果已建成的道路少于 $N - 1$ 条，则重复步骤 1。
你的任务是编写一个程序来解决 Astro 的问题。
交互
你应该实现一个 run() 函数，该函数将在程序开始时被调用一次。在此函数中，每当你使用 SETI Masterpieces 时，都应该调用 query()。每当你确定了最新建成的道路时，都应该调用 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 Masterpieces 发起查询。参数 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)$ 次调用，程序将终止并返回当前测试用例的得分。否则，Terran 人将建造一条新道路，交互继续进行。任何后续对 query() 的调用都将考虑在调用 setRoad() 之后建造的道路。
你的过程：run()
- C/C++:
void run(int N); - Pascal:
procedure run(N : longint);
你的提交必须实现此过程。你必须在此过程中交替调用 query() 和 setRoad()。接收到的参数 $N$ 表示 Terran 人建造的城市数量。如果此过程在猜出所有道路之前结束执行，你将不会获得该测试用例的分数。
语言说明
- C/C++: 你必须
#include “icc.h” - Pascal: 你必须定义
unit icc，并且必须使用语句uses graderhelplib导入评测程序例程。
子任务
此任务的测试用例分为 6 个批次。属于同一批次的测试具有相同的 $N$ 值。如果你在批次中的每个测试中，使用最多 $M$ 次 query() 函数调用正确猜出了所有道路，你将获得该批次的分数。各批次的 $N$、$M$ 值以及分数如下表所示。
| 批次编号 | $N$ = 城市数量 | $M$ = 最大 query() 调用次数 |
分数 |
|---|---|---|---|
| 1 | 15 | 1500 | 7 |
| 2 | 50 | 2500 | 11 |
| 3 | 100 | 2250 | 22 |
| 4 | 100 | 2000 | 21 |
| 5 | 100 | 1775 | 29 |
| 6 | 100 | 1625 | 10 |
样例
样例 1
Contestant action: run(4)
Grader action: -
Note: The grader starts a run for N = 4 cities. The first road is built between cities 2 and 4, unknown to the contestant.
Contestant action: query(1, 3, {1}, {2, 3, 4})
Grader action: return 0
Note: Query for sets {1} and {2, 3, 4}. The answer is "false": there is no road from 1 to any of the other cities.
Contestant action: query(1, 2, {2}, {3, 4})
Grader action: return 1
Note: Query for sets {2} and {3, 4}. The answer is "true": there is a road from city 2 to city 4.
Contestant action: query(1, 1, {2}, {3})
Grader action: return 0
Contestant action: setRoad(2, 4)
Grader action: -
Note: The contestant guesses correctly road (2, 4). The grader generates a new road between 1 and 3.
Contestant action: query(2, 2, {2, 4}, {1, 3})
Grader action: return 0
Note: Query for sets {2, 4} and {1, 3}. The answer is "false".
Contestant action: setRoad(1, 3)
Grader action: -
Note: The contestant guesses correctly road (1, 3). The grader generates a new road between 1 and 4.
Contestant action: query(2, 2, {2, 4}, {1, 3})
Grader action: return 1
Note: Same query as the last one. The answer is now "true", because of the newly generated road.
Contestant action: query(1, 2, {2}, {1, 3})
Grader action: return 0
Contestant action: query(1, 1, {4}, {3})
Grader action: return 0
Contestant action: setRoad(4, 1)
Grader action: exit
Note: The contestant guesses correctly the last road (4, 1). The grader accepts the last guess and gives full score for the test.