Problem E
Debellatio

“I’m never satisfied unless I get the last word.” ­–Alan Dershowitz.

When representing their clients in front of a clueless jury, seasoned lawyers know that rhetoric can be just as, if not more, important than actual substance. It is imperative to make the other side look like a fool; sometimes, the actual content of the argument is immaterial, and the winner of the argument is simply the one who has the last word.

As is the case now.

You are a lawyer representing your client in a high-profile case, and the time has come to demonstrate your sharp wit and destroy the opposing side’s lawyer in the courtroom.

There are $N$ arguments, labelled $1, 2, \dots , N$ respectively. There are $M$ relations between these arguments; the $i^\text {th}$ relation means that arguments $A_ i$ and $B_ i$ are related, which means one can be used as a rebuttal for the other, and vice-versa. Both of you know all these arguments and relations.

Of course, it is important to remember that:

• When arguing, you and your opponent will be taking turns.

• It is important to ensure that arguments are related to the previous one. If you make an argument that is not related, your opponent will call non sequitur and you will immediately lose the argument. (The same holds for your opponent.)

• No arguments can be repeated. If you make an argument that has already been made, the audience will realize that you are wasting their time, and you will immediately lose the argument. (The same holds for your opponent.)

An argument is called valid if it satisfies the conditions above.

Now, your goal is obviously to strategically argue in such a way to trap your opponent into a corner and make him look like a fool.

Your opponent is so convinced he will win that he even gave you the choice of who you want to go first. Let hubris be his downfall, and annihilate your opponent completely in this battle of wits!

Interaction

First, your program should read two integers $N$ ($2 \leq N \leq 70$) and $M$ ($1 \leq M \leq \frac{N(N-1)}{2}$), the number of arguments and the number of relations, respectively, on a single line from standard input.

Then, your program should read $M$ lines from standard input. The $i^\text {th}$ of these lines contains $A_ i$ and $B_ i$ ($1 \leq A_ i, B_ i \leq N$; $A_ i \neq B_ i)$, the two arguments related by the $i^\text {th}$ relation.

Then, your program writes a single line containing a single integer $1$ or $2$ to the standard output, denoting whether you want yourself or your opponent to go first, respectively.

Then, we repeat the following process:

• If it is your turn:

  • Your program writes a single line containing a single integer $a$ ($0 \leq a \leq N)$ to standard output, the label of the argument you wish to make. An output of $0$ denotes that you wish to concede the argument; in this case, your program should terminate immediately after this.

• If it is your opponent’s turn:

  • Your program should read a single integer $a$ ($0 \leq a \leq N)$ from standard input, the label of the argument your opponent made. An input of $0$ denotes that your opponent has conceded the argument; in this case, your program should terminate immediately after this.

After making an argument, do not forget to output end of line and flush the output. To do this, use:

• fflush(stdout) or cout.flush() in C++;

• System.out.flush() in Java;

• stdout.flush() in Python;

• see documentation for other languages.

You can assume that any relation between two arguments will be described at most once.

You can assume that the arguments your opponent makes are always valid, and your opponent will concede if and only if he has no valid argument. Likewise, all your arguments must be valid, and you must win the argument­–that is, have the last word­–for your solution to be correct.

Sample interaction