P9323 [EGOI 2022] Toy Design / 玩具设计
题目背景
Day 2 Problem C.
题面译自 [EGOI2022 toydesign](https://stats.egoi.org/media/task_description/2022_toydesign_en.pdf)。
[](https://creativecommons.org/licenses/by-sa/3.0/)
题目描述
**本题是一道 Grader 交互题。**
你在一个设计玩具的公司工作。一个将被制作的玩具如下：有 $n$ 个大头针，编号从 $1$ 到 $n$，从盒子中伸出。几对大头针被铁丝在盒子中相连。（换句话说，大头针和铁丝组成了一个无向图，其中大头针是节点、铁丝是边。）铁丝无法从盒子外部看到，唯一获得关于他们的信息的方法是对大头针使用一个**检测器**：我们选择两个大头针 $i,j$（$i\ne j$），检测器会告诉你这两个大头针是否连通，包括直接和间接。（因此，检测器告诉你图中这两个大头针之间是否有一条路径。）
我们称一组连接方式为玩具的**设计方案**。
你正在使用一个专用的软件来查询和进行设计。软件工作方式如下：从某个称为“$0$ 号方案”的设计方案开始。他不会告诉你盒子内部的铁丝是什么样的。你需要重复进行以下的三步操作：
1. 选择一个设计方案 $a$ 和两个大头针 $i,j$（$i\ne j$）。
2. 软件告诉你对这两个大头针使用检测器的结果。换句话说，它告诉你在设计方案 $a$ 中 $i$ 与 $j$ 是否（直接或间接地）连通。
3. 同时，如果这两个大头针在设计方案 $a$ 中没有被直接或间接地连接，它会创建一个新的设计方案，包含设计方案 $a$ 中的所有铁丝，同时添加一个直接连接 $i,j$ 的铁丝。这个设计方案的编号为下一个可用的编号。（所以，第一个创建的设计方案是 $1$ 号方案，然后是 $2$ 号，以此类推。）请注意这不会修改设计方案 $a$，只会新建一个设计方案包含新的铁丝。
你的目标是使用这种操作获取尽可能多的 $0$ 号方案的信息。
请注意并不总是可能求出 $0$ 号方案的准确的铁丝连接方式，因为无法区分直接和间接的连接。例如，考虑如下的两种 $n=3$ 的设计方案：
检测器会认为两种方案中任意一对大头针都连通，所以我们无法利用上述软件区分它们。
你的目标是求出任何一种设计方案，使得它与 $0$ 号方案等价。两种设计方案**等价**当且仅当对于任意一对大头针，检测器在两种方案中都返回相同结果。
输入格式
无
输出格式
**交互方式**
你需要实现一个函数：
```cpp
void ToyDesign(int n, int max_ops);
```
作用是给出一种与 $0$ 号方案*等价*的设计方案。你可以调用以下两个函数来实现这一点。你可以调用的第一个函数为：
```cpp
int Connected(int a, int i, int j);
```
其中 $1\le i,j\le n$，$i\ne j$，$a\ge 0$，且 $a$ 不能超过目前已有的设计方案数。如果在设计方案 $a$ 中，大头针 $i,j$ 是（直接或间接地）连通的，它的返回值是 $a$。否则，它的返回值是已有的设计方案数加一，就是包含 $a$ 的所有铁丝以及一根连接 $i,j$ 的铁丝的新的设计方案的编号。函数 `Connected` 可以被调用最多 `max_ops` 次。
当你的程序完成了需要的 `Connected` 调用，它应该描述一种等价于 $0$ 号方案的设计方案。为了描述一个方案，程序应当调用：
```cpp
void DescribeDesign(std::vector result);
```
参数 `result` 是整数对的向量，描述大头针之间的直接铁丝连接。每对数描述一根铁丝，包含被连接的两个大头针的编号。在任意一对（无序的）大头针对之间必须只有至多一根铁丝，且不能有铁丝连接一个大头针和它自己。一旦调用这个函数，你的程序将被终止。
说明/提示
**样例交互过程**
|选手程序|Grader|解释|
|:-|:-|:-|
||`ToyDesign(4, 20)`|玩具中有 $4$ 个大头针。你需要在 $20$ 次 `Connected` 调用内，给出任何一种等价于 $0$ 号方案的设计方案。|
|`Connected(0, 1, 2)`|返回 $1$。|大头针 $1,2$ 在 $0$ 号方案中不直接或间接地连通。新的设计方案是 $1$ 号。|
|`Connected(1, 3, 2)`|返回 $2$。|大头针 $3,2$ 在 $1$ 号方案中不直接或间接地连通。新的设计方案是 $2$ 号。|
|`Connected(0, 3, 4)`|返回 $0$。|大头针 $3,4$ 在 $0$ 号方案中直接或间接地连通。没有新的设计方案。|
|`DescribeDesign({{3, 4}})`||描述一个只有一根铁丝的设计方案：连接大头针 $3,4$。|
---
**数据范围**
对于全部数据，$2\le n\le 200$。
- 子任务一（$10$ 分）：$n\le 200$，`max_ops` 为 $20000$。
- 子任务二（$20$ 分）：$n\le 8$，`max_ops` 为 $20$。
- 子任务三（$35$ 分）：$n\le 200$，`max_ops` 为 $2000$。
- 子任务四（$35$ 分）：$n\le 200$，`max_ops` 为 $1350$。