我有一个由 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
注意
第一个示例的旧图:
第一个示例可能的新图表:
在第二个示例中,我们无法创建任何新图。
第三个例子的旧图:
第三个示例的可能的新图表: