题目描述

给定一个简单的连通无向图，有 $N$ 个顶点和 $M$ 条边。顶点编号为 $1$ 到 $N$，第 $i$ 条边连接了顶点 $A_i$ 和顶点 $B_i$。Takahashi 将为图中的每条边分配两个可能的方向之一，形成一个有向图。确定是否可以构建一个每个顶点都有偶数条出边的有向图。如果答案是肯定的，请构建一个这样的图。

注意事项

当一个无向图中不包含自环或多重边时，称之为简单无向图。

约束条件

• $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$ 和 $4$ 没有出边。

示例输入2

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

示例输出2

-1