Problem description

Jasio zapisał się na Internetowy Turniej Programistyczny, w którym bierze udział N zawodników. Z podekscytowaniem oczekuje na rywalizację i chciałby już teraz dowiedzieć się, które miejsce może zająć. Na szczęście Jasio zna się na ludziach i potrafi porównać umiejętności niektórych uczestników między sobą. W szczególności wyznaczył już M par (a_i, b_i), co do których jest przekonany, że zawodnik o numerze a_i uzyska wyższe miejsce (miejsce o mniejszym numerze) w turnieju od zawodnika o numerze b_i.

Twoim zadaniem jest napisanie programu, który na podstawie podanych przez Jasia informacji określi najwyższe oraz najniższe miejsce, jakie może on zająć w Turnieju.

Jasio oczywiście mógł się pomylić i podać sprzeczne informacje,¹ co również powinno zostać wykryte przez Twój program.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i M, oznaczające odpowiednio liczbę zawodników oraz liczbę informacji podanych przez Jasia.

W i-tym z kolejnych M wierszy znajdują się dwie różne liczby naturalne a_i i b_i, oznaczające, że zawodnik o numerze a_i uzyska lepszy wynik od zawodnika o numerze b_i.

Uczestnicy są ponumerowani liczbami naturalnymi od 1 do N, a Jasio jest zawodnikiem o numerze 1.

Zagwarantowane jest, że wszystkie uporządkowane pary (a_i, b_i) są parami różne.

Wyjście

Program powinien wypisać dwie liczby naturalne, oddzielone spacją, oznaczające odpowiednio najwyższe oraz najniższe miejsce, na którym może znaleźć się Jasio. W przypadku sprzecznych informacji, zamiast tego należy wypisać jedno słowo NIE.

Ograniczenia

1 ≤ N ≤ 1 000 000, 0 ≤ M ≤ 1 000 000

Przykład

4 4
2 4
1 3
2 1
4 3

2 3

5 4
2 1
3 2
1 3
4 5

NIE

3 2
1 2
2 3

1 1