分数: 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