問題文

$N$ 頂点 $M$ 辺の有向グラフがあります。 このグラフが単純グラフであるとは限りませんが、自己ループはもちません。 頂点は $1$ から $N$ の番号で区別されます。 $i$ 番目の辺は頂点 $U_i$ から出て頂点 $V_i$ に向かっています。 各頂点 $x$ について、頂点 $x$ から出る辺の個数を $p_x$ 、頂点 $x$ に向かう辺の個数を $n_x$ として、 $d_x=p_x-n_x$ とします。

このグラフから $0$ 個以上の辺を選んで取り除くことで、新しいグラフを作ります。 このとき、新しいグラフとしてあり得るものであって、次の条件をすべて満たすものが存在するかどうか判定し、存在するならば $1$ つ求めてください。

• 各頂点 $x$ について、元のグラフと比べて $d_x$ の値が変化していない。
• サイクルをもたない。

求めたグラフは、入力と同じ形式で出力してください。

制約

入力は次の制約を満たします。

• $1 \leq N \leq 300\, 000$
• $0 \leq M \leq 300\, 000$
• $1 \leq U_i , V_i \leq N$
• $U_i \neq V_i$
• 値はすべて整数

入力

$N$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

出力

条件を満たす新しいグラフが存在しない場合は、 -1 という $1$ 行のみ出力してください。

存在する場合は、そのグラフを入力と同じ形式で出力してください。 問題文の条件を満たすグラフが複数ある場合、どれを出力しても構いません。 辺の順番は問いません。 念のため、最後は改行してください。

サンプル

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

5 4
1 2
1 5
2 4
5 2

5 3
1 3
3 4
1 2

10 20
7 5
3 2
5 2
2 1
3 5
10 3
6 7
8 6
5 3
7 3
5 1
8 7
2 3
2 6
2 4
10 5
1 8
2 4
10 9
10 2

10 10
5 2
2 1
10 3
8 6
2 3
2 4
10 5
2 4
10 9
10 2