← 返回题目列表

Codeforces · 329/C

C. 图重建

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

我有一个由 n 个节点组成的无向图,编号为 1 到 n。每个节点最多有两个关联边。对于每对节点,最多有一条边连接它们。没有边将节点与其自身连接。

我想以这样的方式创建一个新图表:

- 新图由与旧图相同数量的节点和边组成。
- 第一段中的属性仍然有效。
- 对于每两个节点 u 和 v,如果旧图中有一条边连接它们,则新图中没有连接它们的边。

帮助我构建新图表,或者告诉我是否不可能。

输入

第一行由两个空格分隔的整数组成:n 和 m (1 ≤ m ≤ n ≤ 105),分别表示节点和边的数量。然后是 m 行。 m 行中的每一条由两个空格分隔的整数 u 和 v (1 ≤ u, v ≤ n; u ≠ v) 组成,表示节点 u 和 v 之间的边。

输出

如果无法构造具有上述属性的新图,则输出由 -1 组成的单行。否则,输出正好 m 行。每行应包含边缘的描述,其方式与输入格式中使用的方式相同。

示例

输入 #1

8 7
1 2
2 3
4 5
5 6
6 8
8 7
7 4

输出 #1

1 4
4 6
1 6
2 7
7 5
8 5
2 8

输入 #2

3 2
1 2
2 3

输出 #2

-1

输入 #3

5 4
1 2
2 3
3 4
4 1

输出 #3

1 3
3 5
5 2
2 4

注意

第一个示例的旧图:

第一个示例可能的新图表:

在第二个示例中,我们无法创建任何新图。

第三个例子的旧图:

第三个示例的可能的新图表: