W Seoul Science High School jest $N$ nauczycieli i $N$ uczniów. Każdy uczeń kupił $N$ kwiatów, ponieważ jutro w Korei jest Dzień Nauczyciela. Jednak jeden z uczniów zrezygnował z nauki i teraz w szkole pozostało tylko $N-1$ uczniów.

Nauczyciele są bardzo zazdrośni, więc wystawią uczniowi ocenę F, jeśli otrzymają od niego mniej kwiatów niż inni nauczyciele. Dlatego każdy nauczyciel powinien otrzymać dokładnie $N-1$ kwiatów. Uczeń może dać kwiaty tylko nauczycielom, którzy go uczyli, a ty wiesz, którzy uczniowie uczyli się u których nauczycieli.

Younghun jest uczniem Seoul Science High School i potrzebuje twojej pomocy w organizacji tego wydarzenia.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $N$ i $M$ ($2 \le N \le 100 000$, $1 \le M \le 200 000$), opisujące liczbę nauczycieli oraz liczbę par (uczeń, nauczyciel), w których uczeń uczył się u nauczyciela.

Następne $M$ wierszy opisuje relacje: $j$-ty wiersz zawiera dwie liczby całkowite $s_j$, $t_j$ ($1 \le s_j \le N-1$, $1 \le t_j \le N$), oznaczające, że $s_j$-ty uczeń może dać kwiaty $t_j$-temu nauczycielowi. Gwarantuje się, że wszystkie pary są różne.

Wyjście

Jeśli nie da się dać wszystkim nauczycielom takiej samej liczby kwiatów ($N-1$ kwiatów), wypisz w pierwszym wierszu pojedynczą liczbę $-1$.

W przeciwnym razie twój program powinien wypisać $M$ wierszy. W $j$-tym wierszu powinna znaleźć się pojedyncza liczba całkowita oznaczająca liczbę kwiatów, które $s_j$-ty uczeń dał $t_j$-temu nauczycielowi.

Jeśli istnieje wiele możliwych odpowiedzi, możesz wypisać dowolną z nich.

Przykład

Wejście 1

6 12
1 3
1 4
1 5
2 2
2 4
3 1
3 3
4 1
4 2
4 4
5 4
5 6

Wyjście 1

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

Wejście 2

6 12
1 2
1 3
1 4
2 2
2 4
3 1
3 3
4 1
4 2
4 4
5 5
5 6

Wyjście 2

-1