The Bajtocka Space Agency discovered the asteroid BA-1T several years ago. Bajtazar is overseeing the mission of an unmanned research probe tasked with bringing mineral samples found there back to Earth. Unfortunately, incompetent programmers introduced many bugs into the probe's system, making communication with it very difficult. Despite this, Bajtazar must complete the mission.

Bajtazar has identified $n$ important points on the asteroid from which mineral samples must be collected. The points are numbered with natural numbers from 1 to $n$, and the probe is initially located at point 1. There are a certain number of bidirectional connections between these points. If the probe is at one end of a connection, it can move to the other end. Unfortunately, information about the connections was encoded in the probe, and Bajtazar does not know them. Fortunately, he remembers that the probe can get from any point to any other point, possibly using other intermediate points.

In theory, the matter is simple. Bajtazar can issue movement commands to the probe to any other point, and the probe should inform Bajtazar whether the move was successful.

In practice, however, it is a bit more complicated due to software bugs. First, if Bajtazar orders a move to the point where the probe is currently located, the device will explode, and conducting research will be impossible. If a direct connection to the destination point does not exist, the probe will not change its position, and Bajtazar will receive a negative response. If, however, a connection exists, the probe will move there. But due to another software bug, Bajtazar will receive a positive response only if the probe performs an even-numbered successful move. Otherwise, he will receive a negative response—exactly the same as in the case of no connection.

The probe can also examine the point where it is currently located (i.e., collect material samples). However, to maintain order in the research, each point must be examined exactly once.

Since the probe is far from Earth, issuing commands is very time-consuming, so Bajtazar can issue at most one million movement commands.

Help Bajtazar conduct the research and restore the Agency's faith in their mission!

Interaction

This is an interactive task. You must write a program that will communicate with the probe using the provided library. To do this, you must include the header sonlib.h using the directive:

#include "sonlib.h"

The library provides the following functions:

• int GetN() – Returns the parameter $n$ ($3 \le n \le 400$), which is the number of important points on the asteroid.
• int GetSubtask() – Returns the parameter $s$ ($0 \le s \le 3$) described below in the "Subtasks" section.
• int MoveProbe(int v) – Issues a command to the probe to move to point $v$. Then:
  • If the condition $1 \le v \le n$ is not met, the probe is currently at point $v$, or if the program has previously issued 1,000,000 MoveProbe commands, the program's execution is terminated, and the test result is an incorrect answer.
  • If there is no connection from the current point to $v$, the probe does not move, and the function returns 0.
  • If a connection from the current point to $v$ exists, the probe moves to point $v$. If this is an even-numbered successful move of the probe (for example, the second or tenth), the function returns 1. Otherwise, the function returns 0.
• void Examine() – Issues a command to the probe to examine the point where it is currently located. Then:
  • If the probe attempts to examine a point that has already been examined, the program's execution is terminated, and the test result is an incorrect answer.
  • If the probe has examined every point exactly once, the library terminates the program, accepting the solution.

The program will be terminated by the library by calling the exit(0) command.

The probe is initially located at point 1. The connections allow visiting all points (the graph is connected). The connections are fixed at the beginning of the program's execution, i.e., the library will not change them based on previous queries.

Deliberate attempts to influence the internal operation of the grading library are prohibited.

Subtasks

In all tests, $3 \le n \le 400$. Your program can call the MoveProbe function at most 1,000,000 times.

Some points for this task can be obtained by solving subtasks where the graph of connections between points has a special form. The GetSubtask function returns the parameter $s$, which allows detecting these subtasks:

• If $s = 0$, the graph does not have to satisfy any additional assumptions.
• If $s = 1$, the connection graph is a complete bipartite graph. The set of points can then be divided into two (unknown) non-empty subsets $A, B$. There are then $|A| \cdot |B|$ connections. Each of them connects a point from set $A$ and a point from set $B$.
• If $s = 2$, the existence of three specific connections is guaranteed: between the pair of points $(1, 2)$, between the pair of points $(2, 3)$, and between the pair of points $(3, 1)$.
• If $s = 3$, each point is connected to exactly two other points.

You can assume that every test within a single group of tests has the same value of the parameter $s$.

Examples

Input 1

(The library provides the following data based on the graph: (1, 2), (1, 3), (2, 3), (2, 4))

Output 1

Bajtazar issued a total of 5 MoveProbe commands, which is within the limit of 1,000,000 commands.

Experiments

An example incorrect solution and an example library can be found in the archive in the Pliki (Files) section on SIO. The library may differ in behavior from the one that will be used to evaluate solutions and may not meet the task's assumptions. It is only intended to show how to interact with the program.

The son.cpp solution can be compiled as follows:

g++ -O3 -static -o son son.cpp sonlib.cpp -std=c++17

You must ensure that the sonlib.h and sonlib.cpp files are in the same folder as the solution.

After compilation, the library accepts the graph on standard input. The first line of input should contain three numbers $n, m, s$ – the number of important points, the number of connections between them, and the subtask number, respectively. Each of the next $m$ lines should contain two point numbers that are the endpoints of a given connection. The input file corresponding to the example test is in the archive in the file son0.in.