This is an interactive problem.

Given a graph of nodes numbered from to , you need to find all undirected edges through some operations.

Each node has a mark , which is set to initially. now you can apply 4 kinds of operations:

`modify(x)`

: For node and all of 's direct neighbors, change each node's mark from to ( denotes the exclusive or).`query(x)`

: Return the current value of node .`report(x,y)`

: Record that there is an edge between and .`check(x)`

: Check if all edges incident on have been reported.

For each operation, you can use them at most , , , and times, respectively.

Your job is to implement the function `explore(N,M)`

. `N`

and `M`

denote the number of nodes and edges respectively.

With the header `explore.h`

, you can call these four functions:

`modify(x)`

: There will be no return value. Please make sure .`query(x)`

: It will return the value of node . Please make sure .`report(x,y)`

: It will record an edge between nodes and . Please make sure .`check(x)`

: It will return the status of node . Please make sure . It will return when all edges connected with have been recorded. It will return otherwise.

Note that all graphs are fixed in advance and won't change.

#### Implementation details

##### Interface (API)

To be implemented by contestant:

```
void explore(int N, int M);
```

Provided for your usage:

```
void modify(int p);
int query(int p);
void report(int x, int y);
int check(int x);
```

#### Grading

There are a total of 25 test cases, each worth 4 points. The constraints for each case is as follows:

Test Case | Additional Constraints | |||||
---|---|---|---|---|---|---|

1 | None | |||||

2 | ||||||

3 | ||||||

4 | ||||||

5 | ||||||

6 | A | |||||

7 | ||||||

8 | ||||||

9 | ||||||

10 | B | |||||

11 | ||||||

12 | C | |||||

13 | ||||||

14 | ||||||

15 | D | |||||

16 | ||||||

17 | ||||||

18 | None | |||||

19 | ||||||

20 | ||||||

21 | ||||||

22 | ||||||

23 | ||||||

24 | ||||||

25 |

If a test case is labeled `A`

, then every node in the graph has degree 1.

If a test case is labeled `B`

, then for every node , there exists exactly one node directly connected to it.

If a test case is labeled `C`

, then there exists a permutation of the first nonnegative integers such that two integers are adjacent in the permutation if and only if an edge connects them.

If a test case is labeled `D`

, then the graph is connected.

#### Hint

You can look at the units digit of to distinguish the special graphs from the other cases.

## Comments