Rekonstrukcja grafu

To zadanie pochodzi z Codeforces. Tam też znajdują się testy do zadania.
Jeśli Twoje rozwiązanie zostanie pozytywnie ocenione na tamtych testach, należy wysłać tu zgłoszenie wypisujące "Zrobione".

Limit pamięci: 256MB

Mamy dany graf G taki, że stopień każdej krawędzi wynosi co najwyżej 2.
Stwórz graf G' o takiej samej liczbie krawędzi taki, że jeśli krawędź v należy do G', to nie należy do G.
Tworzony graf również musi mieć stopnie maksymalnie wielkości 2.

Wejście

W pierwszym wieszu znajdują się dwie liczby całkowite n, m (n, m<=105) oznaczające liczbę wierzchołków i krawędzi z grafie G.
W następnych m wierszahc podane są pary liczb reprezentujące krawędzie w tym grafie (wierzchołki numerujemy od 1, nie ma pentli).

Wyjście

Na wyjście wypisz m par liczb prezentujących krawędzie w grafie G' (tak jak na wejściu), lub -1, jeśli nie istnieje graf G'.
Jeśli jest wiele poprawnych odpowiedzi, wypisz dowolną.

Przykład

Wejście:
8 7
1 2
2 3
4 5
5 6
6 8
8 7
7 4


Wyjscie:
1 4
4 6
1 6
2 7
7 5
8 5
2 8

Wejście:
3 2
1 2
2 3

Wyjscie:
-1
Wejście:
5 4
1 2
2 3
3 4
4 1

Wyjscie:
1 3
3 5
5 2
2 4