Today is CC's birthday, and Little K has carefully prepared a birthday gift for her. However, to make things a bit difficult for her, he does not want to give her the gift directly, but rather wants her to find it herself.

At CC's birthday party, Little K mysteriously brings out $n$ small treasure chests, each with a different weight. Little K has announced some of the weight relationships between the chests in advance, and then tells CC that the birthday gift is hidden in the second-heaviest chest. However, he does not tell her which one it is, leaving her to find it herself. CC only has a balance scale at her disposal, which allows her to compare the weights of two chests at a time. She wants to find the second-heaviest chest using as few comparisons as possible, because Little K told her that if her strategy guarantees the minimum number of comparisons in the worst case, she will receive an extra surprise!

Input

The first line contains an integer $n$, representing the number of treasure chests. The second line contains an integer $m$, representing the number of weight relationships announced in advance. The following $m$ lines each contain two integers $x$ and $y$ ($1 \le x, y \le n$), indicating that chest $x$ is heavier than chest $y$.

Constraints

• $2 \le n \le 200000$
• $2 \le m \le 200000$
• The announced relationships are consistent.

Interaction

This is an interactive problem. Your program can only access the input file gift.in and interact with the testing library.

The input file format is as described above. The testing library provides several functions, which are used as follows:

• init must be called first, and only once, to initialize the testing library.
• compare(x, y) compares the weight of chest $x$ and chest $y$, where $1 \le x, y \le n$. If chest $x$ is heavier than chest $y$, it returns $1$; otherwise, it returns $-1$.
• answer(x) reports the result to the testing library, where $x$ is the index of the second-heaviest chest. Once this function is called, the testing library will automatically terminate your program.

Implementation Details

For Pascal users: Your program should reference the testing library using: uses gift_lib_p; The prototypes for the library functions are: procedure init; function compare(x, y: longint): longint; procedure answer(x: longint);

For C/C++ users: You should create a project, include the file gift_lib_c.o, and add the following line to the beginning of your program: #include "gift_lib_c.h" The prototypes for the library functions are: void init(); int compare(int, int); void answer(int);

Testing Your Program

• In addition to creating gift.in as described above, please create another file named gift.dat. This file should contain $n$ distinct integers, with absolute values not exceeding $2 \times 10^9$, representing the weights of each chest in order.
• When you execute your program, the testing library will generate an output file gift.log, which contains the record of interactions between your program and the library, as well as the final result.
• If the program terminates normally, the last line of gift.log will contain an integer representing the number of queries you made.
• If the program terminates abnormally, we do not guarantee that the contents of gift.log will be meaningful.
• During official testing, the testing library will generate the weights of the chests itself and will try to make each answer as unfavorable to you as possible.

Examples

Input 1

3
1
3 2

Output 1

init;
compare(3,1);
compare(2,1);
answer(1);

Note

This example is only for illustrating the use of library functions and has no algorithmic significance.

Subtasks

If your program meets any of the following conditions, the test case will receive 0 points: Terminates on its own; Calls library functions illegally; * Causes the testing library to exit abnormally.

Otherwise, the score for the test case is calculated according to the following formula:

$$ YourScore = \begin{cases} 0 & YourAnswer > n + \lceil \log_2 n \rceil \\ 1 & YourAnswer > BestAnswer + 2 \\ 4 & YourAnswer = BestAnswer + 2 \\ 7 & YourAnswer = BestAnswer + 1 \\ 10 & YourAnswer = BestAnswer \end{cases} $$

Where $YourAnswer$ is the number of comparisons made by your program, and $BestAnswer$ is the number of comparisons under the optimal strategy.

Note

The input size is quite large; please choose an efficient way to read the input.