Problem Statement

This is an interactive problem (a problem in which your program and the judge system communicate through input and output).

There is a graph $G$ with $N$ vertices numbered from $1$ to $N$. Initially, $G$ has no edges.

Perform the following interaction $M$ times so that $G$ contains no cycle after the interactions are finished.

In the $i$-th interaction, integers $A_i,B_i$ are given. Add to $G$ either a directed edge from vertex $A_i$ to vertex $B_i$ or a directed edge from vertex $B_i$ to vertex $A_i$.

Constraints

• $3 \leq N \leq 2 \times 10^{4}$
• $1 \leq M \leq \min(3\times 10^{4} , \frac{N(N-1)}{2})$
• $1 \leq A_{i},B_{i} \leq N$ ,$A_i \ne B_i$($1 \leq i \leq M$)
• $i \ne j \Rightarrow \{A_i,B_i\} \ne \{A_j,B_j\}$
• All input values are integers.

Input and Output

This is an interactive problem.

First, $N$ , $M$ are given from standard input in the following format.

$N$ $M$

Then, perform the following interaction $M$ times.

In the $i$-th interaction, $2$ integers $A_{i}$ , $B_{i}$ are given from standard input in the following format.

$A_{i}$ $B_{i}$

On line $i$, output $0$ to add a directed edge from vertex $A_{i}$ to vertex $B_{i}$ to $G$, or $1$ to add a directed edge from vertex $B_{i}$ to vertex $A_{i}$.

After the above input and output are completed, your answer is judged correct if $G$ contains no cycle.

Notes

Sample

4 4
1 2
1 3
1 4
2 3

0
1
0
1