Król Aragorn

To zadanie będzie wykorzystane na obozie Petrozavodsk 2007. Jeśli będziesz na tym obozie, i przypadkiem umiesz po polsku :), to nie czytaj!

Opis

Po pokonaniu złego Saurona, Aragorn, król Gondoru, staje przed kolejenym wyzwaniem. Gospodarka jego królestwa podupadła na skutek długotrwałej wojny i kraj wymaga odbudowy. Na początku, Aragorn chciałby uporządkować; sprawy związane z transportem. W Gondorze jest N (2 ≤ N ≤ 100000) miast, z których niektóre pary są połączone dwukierunkowymi drogami. Całkowita liczba dróg wynosi M (1 ≤ M ≤ 200000). Królowi wiadomo, że podróż pomiędzy każdymi dwoma miastami jest możliwa, jednakże w królestwie panuje całkowity bałagan co do nazw dróg. Dlatego Aragorn chciałby nadać drogom numery ze zbioru liczb od 1 do M, tak by każdy numer był nadany dokładnie jednej drodze.

Życie Aragorna byłoby naprawdę proste, gdyby jego poddani mieli tylko takie wymagania co do numerów dróg. Król wie, że jeśli dla pewnego miasta istnieje liczba P >1 dzieląca numery wszystkich dróg wychodzących z tego miasta, jego mieszkańcy staną się aroganccy i w rezultacie wpadną w sidła władzy podłego Morgotha. Aragornowi z pewnością by się to nie podobało.

Pomóż Aragornowi wprowadzić jego lud w nową erę dobrobytu!

Specyfikacja wejścia

W pierwszej linii będą; podane dwie liczby: N (2 ≤ N ≤ 100000) oraz M (1 ≤ M ≤ 200000) oznaczające odpowiednio liczbę miast oraz dróg w Gondorze. W kolejnych M liniach znajdują się opisy dróg poprzez dwie liczby - numery miast, które dana droga łączy. Miasta numerowane są liczbami od 1 do N. Każda para miast połączona jest co najwyżej jedną drogą, więc każda nieuporządkowana para liczb pojawi się na wejściu co najwyżej raz.

Specyfikacja wyjścia

Jeśli numeracja dróg spełniająca wymagania Aragorna jest niemożliwa, wyjście powinno zawierać dokładnie jedną linię z liczbą -1. W przeciwnym razie Twój program powinien wypisać dokładnie M linii. W i-tej linii powinnien znaleźć się numer przypisany do i-tej drogi w kolejnosci pojawiania się na wejściu zgodnie z zaleceniami króla. Jeśli jest wiele poprawnych wyników, Twój program powinien wypisać dowolny z nich.

Przykłady

Dla danych wejściowych:

4 5
1 2
1 3
1 4
2 4
3 4

jednym z poprawnych wyników jest:

4
1
5
3
2

zaś; dla danych wejściowych:

3 2
1 2
2 3

poprawnym wynikiem jest:

-1