你正在为一家玩具设计公司工作。一款正在开发的新玩具工作原理如下：

盒子里有 $n$ 个引脚，编号从 $1$ 到 $n$，伸出盒外。盒子内部有一些引脚对通过导线连接。（换句话说，引脚和导线构成了一个无向图，其中引脚是顶点，导线是边。）这些导线从外部不可见，了解它们的唯一方法是使用测试仪测试引脚：我们可以选择两个引脚 $i$ 和 $j$，满足 $i \neq j$，测试仪会告诉我们这两个引脚在盒子内部是否直接或间接相连。（因此，测试仪会告知图中这两个引脚之间是否存在路径。）

我们将盒子内部的连接集合称为玩具的设计（design）。

你正在使用专门的软件来查询和创建这些设计。该软件的工作方式如下：它从玩具的某种设计开始，我们将其称为“设计 0”。它不会向你展示该设计中盒子内部的连接情况。相反，你可以重复执行以下三步操作：

1. 你选择一个设计编号 $a$ 以及两个引脚编号 $i$ 和 $j$，满足 $i \neq j$。
2. 软件会告诉你如果我们在那两个引脚上使用测试仪会发生什么。换句话说，它会告诉你引脚 $i$ 和 $j$ 在设计 $a$ 中是否（直接或间接）相连。
3. 此外，如果引脚在设计 $a$ 中没有直接或间接相连，那么它会创建一个新的设计，该设计包含设计 $a$ 中的所有连接，并额外增加一条 $i$ 和 $j$ 之间的直接连接。该设计被赋予下一个可用的设计编号。（因此，以这种方式创建的第一个设计编号为 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$。否则，它会返回目前已创建的设计数量加一，该编号将分配给包含设计 $a$ 的所有连接以及 $i$ 和 $j$ 之间连接的新设计。函数 Connected 最多可以调用 max_ops 次。

当你的程序完成 Connected 操作后，它应该描述一个与设计 0 等价的设计。为了描述一个设计，程序应调用：

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

参数 result 是一个整数对向量，描述了引脚之间的直接连接。每一对对应一个连接，应包含该连接的两个引脚编号。每对（无序）引脚之间最多只能有一个直接连接，且引脚自身之间没有直接连接。调用此函数将终止你的程序执行。

数据范围

• $2 \leq n \leq 200$

子任务

• 子任务 1（10 分）：$n \leq 200$，$max\_ops = 20\,000$
• 子任务 2（20 分）：$n \leq 8$，$max\_ops = 20$
• 子任务 3（35 分）：$n \leq 200$，$max\_ops = 2\,000$
• 子任务 4（35 分）：$n \leq 200$，$max\_ops = 1\,350$

样例

说明

提供的样例评测机 grader.cpp（位于任务附件 ToyDesign.zip 中）从标准输入读取数据，格式如下：

• 第一行包含引脚数量 $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 是你提交给 CMS 的解决方案文件。要使用附件中提供的样例输入运行程序，请在终端输入以下命令：

./solution < input.txt