Background

Day 2 Problem C.

The statement is translated from EGOI2022 toydesign。

Problem Description

This is an interactive problem with a grader.

You work at a company that designs toys. A toy that will be manufactured is as follows: there are $n$ pins, numbered from $1$ to $n$, sticking out of a box. Some pairs of pins are connected by wires inside the box. (In other words, the pins and wires form an undirected graph, where pins are nodes and wires are edges.) The wires cannot be seen from outside the box. The only way to obtain information about them is to use a detector on the pins: we choose two pins $i,j$ ($i\ne j$), and the detector tells you whether these two pins are connected, either directly or indirectly. (So the detector tells you whether there is a path between these two pins in the graph.)

We call a wiring pattern a toy design.

You are using a dedicated software to query and build designs. The software works as follows: it starts from some design called “design $0$”. It will not tell you what the wires inside the box look like. You need to repeatedly perform the following three-step operation:

1. Choose a design $a$ and two pins $i,j$ ($i\ne j$).
2. The software tells you the detector result for these two pins. In other words, it tells you whether $i$ and $j$ are connected (directly or indirectly) in design $a$.
3. At the same time, if these two pins are not connected directly or indirectly in design $a$, it creates a new design that contains all wires from design $a$, and additionally adds one wire directly connecting $i$ and $j$. The number of this design is the next available number. (So the first created design is design $1$, then $2$, and so on.) Note that this does not modify design $a$; it only creates a new design that contains the additional wire.

Your goal is to use this operation to obtain as much information about design $0$ as possible.

Note that it is not always possible to determine the exact wiring of design $0$, because you cannot distinguish direct connections from indirect ones. For example, consider the following two designs with $n=3$:

The detector would report that every pair of pins is connected in both designs, so we cannot distinguish them using the software above.

Your goal is to find any design that is equivalent to design $0$. Two designs are equivalent if and only if, for every pair of pins, the detector returns the same result in both designs.

Output Format

Interaction

You need to implement a function:

void ToyDesign(int n, int max_ops);

Its purpose is to output a design that is equivalent to design $0$. You can do this by calling the following two functions. The first function you can call is:

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

Here $1\le i,j\le n$, $i\ne j$, $a\ge 0$, and $a$ cannot exceed the number of designs currently available. If pins $i$ and $j$ are connected (directly or indirectly) in design $a$, its return value is $a$. Otherwise, its return value is the number of designs currently available plus one, i.e. the index of the new design that contains all wires of $a$ and one extra wire connecting $i$ and $j$. The function Connected can be called at most max_ops times.

After your program has finished making the required Connected calls, it should describe a design equivalent to design $0$. To describe a design, your program should call:

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

The parameter result is a vector of integer pairs describing direct wire connections between pins. Each pair describes one wire and contains the numbers of the two pins it connects. Between any (unordered) pair of distinct pins, there must be at most one wire, and no wire may connect a pin to itself. Once you call this function, your program will be terminated.

Hint

Sample interaction

Constraints

For all testdata, $2\le n\le 200$.

• Subtask 1 ($10$ points): $n\le 200$, max_ops is $20000$.
• Subtask 2 ($20$ points): $n\le 8$, max_ops is $20$.
• Subtask 3 ($35$ points): $n\le 200$, max_ops is $2000$.
• Subtask 4 ($35$ points): $n\le 200$, max_ops is $1350$.

Translated by ChatGPT 5