C. Перестроим граф
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Дан неориентированный граф, состоящий из n вершин, пронумерованных от 1 до n. У каждой вершины есть не более двух инцидентных ребер. Для каждой пары вершин существует не более одного соединяющего их ребра. Ни одно ребро не соединяет вершину с самой собой.

Мне хотелось бы построить новый граф таким образом, чтобы:

  • Новый граф состоял из такого же количества вершин и ребер, что и старый граф.
  • Свойства, указанные в первом абзаце, выполнялись.
  • Для каждых двух вершин u и v, если в старом графе есть соединяющее их ребро, то в новом графе соединяющего их ребра нет.

Помогите мне построить новый граф.

Входные данные

Первая строка содержит два целых числа через пробел, n и m (1 ≤ m ≤ n ≤ 105), обозначающих количество вершин и ребер, соответственно. Далее следуют m строк. Каждая из m строк состоит из двух разделенных пробелом целых чисел u и v (1 ≤ u, v ≤ nu ≠ v), обозначающих ребро между вершинами u и v.

Выходные данные

Если построить новый граф с упомянутыми выше свойствами невозможно, то выведите в единственной строке -1. В противном случае выведите ровно m строк. Каждая строка должна описывать ребро в формате, указанном во входных данных.

Примеры
Входные данные
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
Примечание

Старый граф из первого примера:

Возможный новый граф для первого примера:

Во втором примере мы не можем построить новый граф, удовлетворяющий ограничениям.

Старый граф из третьего примера:

Возможный новый граф для третьего примера: