$N$ 頂点 $M$ 辺の二部グラフ $G$ が与えられます。 $G$ は単純 (多重辺が存在しない) ですが、連結とは限りません。
$i$ 番目の辺は、 $u_i, v_i$ を双方向に結んでいます。 ($1 \le i \le M$)

与えられた $G$ の各頂点を赤か青で塗ります。
以下の条件を満たすとき、その塗り方は「良い彩色」です。

• すべての辺 $e_i = \{ u_i, v_i \}$ に対して、頂点 $u_i, v_i$ が異なる色で塗られている
• 使われない色が存在しない

良い彩色 $\alpha, \beta$ が与えられます。
$\alpha(v), \beta(v)$ は頂点 $v$ の色を表しており、 0 なら赤に、 1 なら青に塗られていることを表しています。

Asa さんは、 $\alpha$ に対して以下の操作を繰り返すことで、 $\alpha$ を $\beta$ に一致させたいです。

• 1 頂点選び、その頂点の色を変える。 ただし、変更後の塗り方も良い彩色でなければならない。

最小で何度の操作をする必要があるかを求め、一致させることができるならばそれを実現する操作列を出力してください。
ただし、何回操作しても $\alpha$ を $\beta$ に一致させることができない場合は、 -1 を出力してください。

• $2 \le N \le 2 \times 10^5$
• $0 \le M \le \min\left( \dfrac{N (N - 1)}{2}, 2 \times 10^5 \right)$
• $1 \le u_i < v_i \le N$
• 任意の頂点 $v$ について、 $\alpha(v), \beta(v) \in \{ 0, 1 \}$
• 与えられるグラフは単純な二部グラフである
• $\alpha, \beta$ はどちらも良い彩色である
• 入力はすべて整数である

部分点

この問題はいくつかの小課題に分けられ、その小課題の全てのテストケースに正解した場合に、「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。

1. (10 点) $N \le 8$ 、かつ、出力した操作回数が正しい
2. (20 点) $N \le 8$ 、かつ、出力した操作回数と操作列が正しい
3. (25 点) 入力に関する追加制約はない、かつ、出力した操作回数が正しい
4. (45 点) 入力に関する追加制約はない、かつ、出力した操作回数と操作列が正しい

入力は以下の形式で標準入力から与えられる。

$\alpha, \beta$ を一致させることができる操作列が存在しない場合は -1 を 1 行で出力せよ。
その他の余計な出力をしてはならない。余計な出力をした場合、小課題 1, 3 の得点も得られない。

操作列が存在する場合は、条件を満たす操作列のうち、操作回数が最小となるものを以下の形式で出力せよ。
ここで、 $t$ は操作回数を表し、 $v_i, c_i (1 \le i \le t)$ は「$i$ 回目の操作で頂点 $v_i$ の色を $c_i$ に変更する」という操作を表す。

答えが複数存在する場合、どれを出力しても正解とみなされる。
ただし、出力は以下の条件を満たす必要がある。

• $1 \le v_i \le N$
• $0 \le c_i \le 1$
• $t, v_i, c_i$ はすべて整数

特に、 $t = 0$ の場合は、 0 を 1 行で出力せよ。
その他の余計な出力をしてはならない。余計な出力をした場合、小課題 1, 3 の得点も得られない。