B - Even Degrees Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 に向かって向き付けられた辺が存在することを表す。 辺は任意の順で出力して構わない。

入力例 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