← 返回题目列表

AtCoder · agc035_b

B. 偶数度

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给你一个简单的连通无向图 N 顶点和 M 边缘。顶点已编号 1 to 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) 表示有一条从 Vertex 指向的边 C_i 到顶点 D_i。边缘可以按任何顺序打印。


示例输入 1

4 4
1 2
2 3
3 4
4 1

示例输出 1

1 2
1 4
3 2
3 4

分配方向后,Vertex 1 和 3 将各有两个出边,并且顶点 2 和 4 每个都有零个传出边缘。


示例输入 2

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

示例输出 2

-1