問題文

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。

$1$ から $N$ の番号がついた $N$ 頂点のグラフ $G$ があります。はじめ $G$ には辺がありません。

以下のやりとりを $M$ 回行って、やりとりを終えた後の $G$ にサイクルが含まれないようにしてください。

$i$ 回目のやりとりでは、整数 $A_i,B_i$ が与えられるので、$G$ に頂点 $A_i$ から頂点 $B_i$ への有向辺か、頂点 $B_i$ から頂点 $A_i$ への有向辺を追加してください。

制約

• $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\}$
• 入力される値は全て整数

入出力

この問題はインタラクティブな問題です。

最初に、 $N$ , $M$ が以下の形式で標準入力から与えられます。

$N$ $M$

次に、以下のやり取りを $M$ 回行ってください。

$i$ 回目のやり取りは、 $2$ つの整数 $A_{i}$ , $B_{i}$ が以下の形式で標準入力から与えられます。

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

$i$ 行目には $G$ に頂点 $A_{i}$ から頂点 $B_{i}$ への有向辺を追加する場合は $0$ を、頂点 $B_{i}$ から頂点 $A_{i}$ への有向辺を追加する場合は $1$ を出力してください。

以上の入出力が完了した後、 $G$ にサイクルが含まれなければ正解となります。

注意

サンプル

4 4
1 2
1 3
1 4
2 3

0
1
0
1