﻿ AGC035 B - Even Degrees - Atcoder

# Home

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