CF329C.Graph Reconstruction

I have an undirected graph consisting of n nodes, numbered 1 through n. Each node has at most two incident edges. For each pair of nodes, there is at most an edge connecting them. No edge connects a node to itself.

I would like to create a new graph in such a way that:

• The new graph consists of the same number of nodes and edges as the old graph.
• The properties in the first paragraph still hold.
• For each two nodes u and v, if there is an edge connecting them in the old graph, there is no edge connecting them in the new graph.

Help me construct the new graph, or tell me if it is impossible.

我有一个由 $n$ 个节点（编号为 $1$ 到 $n$）组成的无向图。每个节点的度数至多为 $2$。任意两个节点之间至多存在一条边，且不存在自环（即没有边连接一个节点到它自身）。

我希望构造一个新图，满足以下条件：

• 新图的节点数和边数与原图相同；
• 第一段中所述的所有性质在新图中依然成立；
• 对于任意两个节点 $u$ 和 $v$，若原图中 $u$ 与 $v$ 之间存在一条边，则新图中 $u$ 与 $v$ 之间不能存在边。

请帮我构造出这个新图，或判断其不可能存在。

The first line consists of two space-separated integers: n and m (1 ≤ m ≤ n ≤ 105), denoting the number of nodes and edges, respectively. Then m lines follow. Each of the m lines consists of two space-separated integers u and v (1 ≤ u, v ≤ n; u ≠ v), denoting an edge between nodes u and v.

第一行包含两个用空格分隔的整数：$n$ 和 $m$（$1 ≤ m ≤ n ≤ 10^5$），分别表示节点数和边数。接下来是 $m$ 行，每行包含两个用空格分隔的整数 $u$ 和 $v$（$1 ≤ u, v ≤ n$；$u ≠ v$），表示节点 $u$ 与节点 $v$ 之间存在一条边。

If it is not possible to construct a new graph with the mentioned properties, output a single line consisting of -1. Otherwise, output exactly m lines. Each line should contain a description of edge in the same way as used in the input format.

如果无法构造出满足上述性质的新图，则输出一行 -1。否则，输出恰好 $m$ 行，每行以与输入格式相同的方式描述一条边。

The old graph of the first example:

A possible new graph for the first example:

In the second example, we cannot create any new graph.

The old graph of the third example:

A possible new graph for the third example:

第一个示例的原始图：

第一个示例的一个可能的新图：

在第二个示例中，我们无法构造任何新图。

第三个示例的原始图：

第三个示例的一个可能的新图：