Contest Duration: ~ (local time) (130 minutes) Back to Home
B - Even Degrees /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

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


出力

C_1 D_1
:
C_M D_M


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

入力例 1

4 4
1 2
2 3
3 4
4 1


出力例 1

1 2
1 4
3 2
3 4


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

入力例 2

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


出力例 2

-1


Score : 700 points

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects Vertex A_i and Vertex B_i. Takahashi will assign one of the two possible directions to each of the edges in the graph to make a directed graph. Determine if it is possible to make a directed graph with an even number of edges going out from every vertex. If the answer is yes, construct one such graph.

Notes

An undirected graph is said to be simple when it contains no self-loops or multiple edges.

Constraints

• 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)
• The given graph is simple and connected.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M


Output

If it is impossible to assign directions to satisfy the requirement, print -1. Otherwise, print an assignment of directions that satisfies the requirement, in the following format:

C_1 D_1
:
C_M D_M


Here each pair (C_i, D_i) means that there is an edge directed from Vertex C_i to Vertex D_i. The edges may be printed in any order.

Sample Input 1

4 4
1 2
2 3
3 4
4 1


Sample Output 1

1 2
1 4
3 2
3 4


After this assignment of directions, Vertex 1 and 3 will each have two outgoing edges, and Vertex 2 and 4 will each have zero outgoing edges.

Sample Input 2

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


Sample Output 2

-1