配点 : $700$ 点

問題文

$N$ 頂点 $M$ 辺の単純連結無向グラフが与えられます。頂点には $1$ から $N$ までの番号がついており、$i$ 本目の辺は頂点 $A_i$ と頂点 $B_i$ を結んでいます。 高橋君は、与えられたグラフのすべての辺にどちらかの向きをつけて有向グラフを作ります。 どの頂点から出る辺の本数も偶数になるような有向グラフを作ることが可能かどうか判定し、可能ならそのような例をひとつ構成してください。

ノート

無向グラフが単純であるとは、自己ループと多重辺を含まないことを指します。

制約

• $2 \leq N \leq 10^5$
• $N-1 \leq M \leq 10^5$
• $1 \leq A_i,B_i \leq N (1\leq i\leq M)$
• 与えられるグラフは単純かつ連結

入力

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

$N$ $M$

$A_1$ $B_1$

$:$

$A_M$ $B_M$

出力

条件を満たす向き付けが不可能な場合、$-1$ を出力せよ。 そうでない場合、以下の形式でグラフのすべての辺の向きを重複なく出力せよ。

$C_1$ $D_1$

$:$

$C_M$ $D_M$

ただし、組 $(C_i,D_i)$ は $C_i$ から頂点 $D_i$ に向かって向き付けられた辺が存在することを表す。 辺は任意の順で出力して構わない。

4 4
1 2
2 3
3 4
4 1

1 2
1 4
3 2
3 4

このように向き付けることで、頂点 $1,3$ からは $2$ 本、頂点 $2,4$ からは $0$ 本の辺が出るようになります。

5 5
1 2
2 3
3 4
2 5
4 5

-1