This is an interactive problem.

Background

After half a year, I-kun's shop finally went out of business. He decided to transfer the shop and become an explorer to explore the vast unknown world.

According to ancient records, he found an underground palace created by an unknown civilization in the heart of a vast desert. The palace consists of $N$ large caves and $M$ bidirectional paths connecting these caves. I-kun can distinguish which cave he is in with the help of the ancient book, but the book does not record the connection structure of the $M$ paths, making it difficult for him to search for the endless treasures hidden in the palace.

However, I-kun has now discovered a mysterious mechanism through which he can learn information about the palace. He has decided to use this mechanism to obtain the connection structure of the palace, and he asks for your assistance.

Description

The underground palace can be abstracted as an undirected simple graph with $N$ vertices and $M$ edges (a simple graph satisfies that there is at most one direct edge between any two points). The caves are numbered from $0$ to $N-1$. Currently, you do not know what the edges are.

Each cave has a light source, which has two states: on and off. A cave is illuminated only when its light source is on. Initially, all light sources are in the off state, and the state of a light source can only be changed using the mysterious mechanism I-kun discovered. Specifically, the mysterious mechanism can perform the following four operations:

1. Given a number $x$ to the mechanism, it will change the state of the light source in cave $x$ and all caves directly connected to cave $x$ by a path. That is, light sources that were previously on will be turned off, and those that were previously off will be turned on.
2. Given a number $x$ to the mechanism, it will display the current state of the light source in cave $x$.
3. Given two numbers $x, y$ to the mechanism, it indicates that you have confirmed there is a path connecting cave $x$ and cave $y$, and the mechanism will record it.
4. Given a number $x$ to the mechanism, it will determine whether all paths connected to cave $x$ have been recorded.

The mechanism can only perform the next operation after completing the previous one. The mechanism cannot be used arbitrarily, so there are limits on the number of times each operation can be used, denoted as $L_m, L_q, M, L_c$ respectively. Your task is to write a program to help I-kun decide how to reasonably use the mysterious mechanism to correctly find all $M$ paths.

Implementation Details

You do not need to, and should not, implement the main function. You only need to implement the function explore(N, M), where $N$ and $M$ represent the number of caves and paths, respectively. You can interact with the interactor by calling the following four functions:

1. modify(x)
   • This function allows the mechanism to perform operation 1 with the given number $x$.
   • You must ensure $0 \le x < N$. This function has no return value.
2. query(x)
   • This function allows the mechanism to perform operation 2 with the given number $x$.
   • You must ensure $0 \le x < N$. This function returns 0 or 1, representing the current state of the light source in cave $x$ as off (0) or on (1).
3. report(x, y)
   • This function allows the mechanism to perform operation 3 with the given numbers $x, y$.
   • You must ensure $0 \le x, y < N$ and $x \neq y$. This function has no return value.
4. check(x)
   • This function allows the mechanism to perform operation 4 with the given number $x$.
   • You must ensure $0 \le x < N$. This function returns 0 or 1, where it returns 1 if and only if all paths connected to cave $x$ have been recorded via operation 3.

During evaluation, the interactor will call explore exactly once.

This problem guarantees that the graph used is completely determined before the interaction begins and will not be dynamically constructed based on your program's interaction process. Therefore, the interactive operations in this problem are deterministic, and you do not need to worry about the specific implementation of these operations in the interactor.

The data guarantees that under the call count limits, the time required for the interactor to run does not exceed 1s; the memory used by the interactor is fixed and does not exceed 128MB.

Implementation Method

A template_explore.cpp/c/pas has been provided in the contestant's working directory. Please copy this file, rename it to explore.cpp/c/pas, and answer the question based on it.

1. For C++ / C language contestants:

   • Please ensure your program starts with #include "explore.h".
   • The interface for the explore function you need to implement is as follows: void explore(int N, int M);
   • The interfaces for the interactive functions you can call are as follows: void modify(int x); int query(int x); void report(int x, int y); int check(int x);

2. For Pascal language contestants:

   • Note: The syntax for implementing the interface in Pascal is more complex. Please answer directly based on the provided template_explore.pas rather than implementing the code from scratch.
   • The interface for the explore function you need to implement is as follows: procedure _explore(N, M : longint);
   • Note: The function name here is _explore rather than explore. Using explore will result in a compilation failure.
   • The interfaces for the interactive functions you can call are as follows: procedure modify(x : longint); function query(x : longint) : longint; procedure report(x : longint; y : longint); function check(x : longint) : longint;

Examples

Input 1

100 200 300
3 2
0 1
1 2

Output 1

Correct

Note

The three integers in the first line of the data represent the call count limits for the three operations, meaning modify(x) cannot be called more than 100 times, query(x) cannot be called more than 200 times, and check(x) cannot be called more than 300 times. The two integers in the second line represent the number of caves and the number of paths, i.e., $N = 3, M = 2$. report(x, y) cannot be called more than $M$ times, which in this example is no more than 2 times.

Scoring

The final evaluation will only collect explore.cpp/c/pas; modifying other files in the contestant's directory will have no effect on the evaluation.

This problem is subject to the same restrictions as traditional problems. For example, compilation errors will result in 0 points for the entire problem, and runtime errors, exceeding time limits, or exceeding memory limits will result in 0 points for the corresponding test cases. You can only access variables and their corresponding memory space defined by yourself and provided by the interactor; attempting to access other spaces may lead to compilation or runtime errors.

Based on the above conditions, you get full marks for a test case if and only if: 1. Each of your function calls is valid, and the number of calls to modify, query, and check does not exceed $L_m, L_q, L_c$, respectively. 2. Since the call limit for report is $M$, each of your calls must record a new and existing edge; that is, each time you call report(x, y), it must satisfy: there is a path connecting cave $x$ and cave $y$, and report(x, y) or report(y, x) has never been called before this call. 3. The explore function you implemented returns normally. 4. When the explore function returns, you have recorded all $M$ paths by calling report.

Constraints

This problem has 25 test cases, each worth 4 points. The data scale and related limits for each test case are shown in the table below.

The meanings of the variables in the special property column are as follows: A: Guarantees that the degree of each vertex is exactly 1. B: Guarantees that for each $x > 0$, there exists exactly one $y < x$ such that cave $x$ and cave $y$ are directly connected by a path. C: There exists a permutation $p_0, p_1, \dots, p_{N-1}$ of $0 \sim N-1$ such that for any $1 \le i < N$, there is a path connecting cave $p_{i-1}$ and $p_i$. D: Guarantees the graph is connected.

• Hint: Your program can distinguish between the different data types mentioned above by checking the last digit of the input $N$.