注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "toydesign.h"。

题目描述

题目译自 European Girls' Olympiad in Informatics 2022 Day2 T3. Toy Design

你正在为一家玩具设计公司工作，他们正在研发一款新玩具。这款玩具的运作方式是这样的：一个盒子上有 $n$ 个插针，编号从 $1$ 到 $n$，有些插针之间通过盒子内部的电线连接在一起。（换句话说，这些插针和电线构成了一个无向图，插针是顶点，电线是边。）这些电线从外面看不到，你唯一能了解它们的方法是用测试仪检测插针：你可以选择两个不同的插针 $i$ 和 $j$（$i \neq j$），测试仪会告诉你这两个插针在盒子内部是否直接或间接连通。（也就是说，测试仪会告诉你图中这两个插针之间是否存在路径。）

我们把盒子里电线的连接方式称为玩具的设计。你将使用一款专门的软件来查询并创建这些设计。这款软件的运作方式如下：它会从某个初始设计开始，我们称之为「设计 $0$」。它不会直接展示设计 $0$ 内部的连接情况，但你可以通过反复执行以下三个步骤来探索：

1. 你选择一个设计编号 $a$ 和两个插针编号 $i$ 和 $j$（要求 $i \neq j$）。
2. 软件会告诉你，如果在设计 $a$ 中用测试仪检测这两个插针会发生什么，也就是说，它会告诉你插针 $i$ 和 $j$ 在设计 $a$ 中是否（直接或间接）连通。
3. 如果插针 $i$ 和 $j$ 在设计 $a$ 中原本没有直接或间接连通，软件会创建一个新设计，这个新设计包含设计 $a$ 的所有连接，外加一条 $i$ 和 $j$ 之间的直接连接。新设计会被分配一个新的编号，从 $1$ 开始依次递增（比如第一个新设计是编号 $1$，第二个是编号 $2$，以此类推）。注意，这个操作不会改变设计 $a$，只是生成一个新的设计。

你的目标是通过这些操作尽可能多地了解设计 $0$。

需要注意的是，你不一定总能完全确定设计 $0$ 的精确连接方式，因为无法区分直接连接和间接连接。例如，假设有 $n=3$ 的两种设计：

在这两种设计中，测试仪对任意一对插针都会报告连通，所以用上述软件无法区分它们。

因此，你的目标是确定一个与设计 $0$ 等价的设计。两个设计如果对所有插针对测试仪的报告结果相同，就称为等价。

交互方式

这是一个交互式问题。你需要实现一个函数：

void ToyDesign(int n, int max_ops);

这个函数的目标是找出一个与设计 $0$ 等价的设计。你需要通过调用以下两个函数来实现这个目标。第一个可调用的函数是：

int Connected(int a, int i, int j);

其中 $1 \leq i, j \leq n$，$i \neq j$，$a \geq 0$，且 $a$ 不能超过当前已创建的设计数量。如果插针 $i$ 和 $j$ 在设计 $a$ 中（直接或间接）连通，函数返回 $a$；否则，它会返回当前已创建的设计数量加 $1$，这个数字会成为新设计的编号。新设计包含设计 $a$ 的所有连接，外加 $i$ 和 $j$ 之间的直接连接。这个函数最多可以调用 $max\_ops$ 次。

当你完成所有连通性操作后，需要描述一个与设计 $0$ 等价的设计。描述设计时，需要调用：

void DescribeDesign(std::vector<std::pair<int,int>> result);

参数 result 是一个整数对向量，用来描述插针之间的直接连接。每个整数对对应一条连接，包含两个插针的编号。每对无序插针之间最多只能有一条直接连接，且插针不能与自身连接。调用这个函数后，你的程序将终止运行。

示例评测程序

任务附件 ToyDesign.zip 中提供的示例评测程序 grader.cpp 会从标准输入读取以下格式的输入：

• 第一行包含插针数量 $n$、直接连接数 $m$ 和 $max\_ops$。
• 接下来的 $m$ 行包含插针对，表示直接连接。

示例评测程序会读取输入并调用你实现的 ToyDesign 函数。根据你的程序行为，评分程序会输出以下消息之一：

• Wrong answer: Number of operations exceeds the limit. —— 如果 Connected 调用次数超过 $max\_ops$。
• Wrong answer: Wrong design id. —— 如果 Connected 的参数 $a$ 指向一个尚未存在的设计编号。
• Wrong answer: Incorrect design." —— 如果 DescribeDesign` 描述的设计与设计 $0$ 不等价。
• OK! —— 如果 DescribeDesign 描述的设计与设计 $0$ 等价。

要将示例评测程序与你的代码一起编译，可以在终端运行以下命令：

g++ -std=gnu++11 -O2 -o solution grader.cpp solution.cpp

其中 solution.cpp 是你要提交的代码文件。要使用附件中的样例输入运行程序，请在终端输入：

./solution < input.txt

样例

数据范围与提示

对于所有输入数据，满足：

• $2 \leq n \leq 200$

详细子任务附加限制及分值如下表所示。