题目描述

给定一个有 $N$ 个顶点 $M$ 条边的简单连通无向图。顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。高桥君想要为给定的图的每一条边指定一个方向，得到一个有向图。请判断是否存在一种方案，使得每个顶点的出边数都是偶数。如果存在，请构造出一种满足条件的方案。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

输出格式

如果不存在满足条件的定向方案，输出 $-1$。
否则，请输出所有边的定向，每行输出一条边的方向，格式如下：

$C_1$ $D_1$
$C_2$ $D_2$
$\vdots$
$C_M$ $D_M$

其中，$(C_i, D_i)$ 表示将第 $i$ 条边定向为从 $C_i$ 指向 $D_i$。边的输出顺序可以任意。

样例 1

输入

4 4
1 2
2 3
3 4
4 1

输出

1 2
1 4
3 2
3 4

样例 2

输入

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

输出

-1

说明/提示

说明

简单图指的是不包含自环和重边的图。

数据范围

• $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)$
• 给定的图保证是简单且连通的。

样例解释 1

如下定向后，顶点 $1,3$ 的出边数为 $2$，顶点 $2,4$ 的出边数为 $0$。

由 ChatGPT 4.1 翻译