Preparando MOJI
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:
Help me construct the new graph, or tell me if it is impossible.
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.
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.
8 7
1 2
2 3
4 5
5 6
6 8
8 7
7 4
1 4
4 6
1 6
2 7
7 5
8 5
2 8
3 2
1 2
2 3
-1
5 4
1 2
2 3
3 4
4 1
1 3
3 5
5 2
2 4
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:
Informação
Provedor Codeforces
Código CF329C
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 08:45:19
Relacionados