Zabytki

Limit pamięci: 64MB

Historia Bajtocji sięga oszałamiających parunastu lat. Nic dziwnego, że w tym znanym wszystkim państwie nie ma żadnych zabytków. Aby zwiększyć turystyczną atrakcyjność państwa, król Bajtazar wybudował n neo-zabytków.

Niestety zabytki bez dobrego dojazdu dla milionów zwiedzających turystów nie są bardzo dochodowe. W związku z tym król postanowił zbudować $m$ jednokierunkowych autostrad; każda autostrada łączy dwa różne zabytki. Budżet Bajtocji pozwala na zbudowanie jednej autostrady tygodniowo. Król stworzył listę autostrad i ustalił kolejność, w jakiej będą budowane.

Ty zaś zostałeś zatrudniony przez nowo powstającą agencję turystyczną BajtoTravel. Twoi mocodawcy chcą wiedzieć, w którym momencie będzie można zorganizować wycieczkę, która zacznie się przy którymś z zabytków, objedzie kilka innych zabytków (poruszając się już wybudowanymi autostradami) i wróci do zabytku, z którego zaczęła.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite n i m (2 <= n <= 1 000 000, 1 <= m <= 1 000 000), oznaczające odpowiednio liczbę neo-zabytków w Bajtocji i liczbę planowanych autostrad. Zabytki są ponumerowane liczbami od 1 do n. Kolejne m wierszy zawiera opis planowanych autostrad; w wierszu i+1 są dwie różne liczby całkowite a_i i b_i (1 <= a_i, b_i <= n) oddzielone pojedynczym odstępem, oznaczające że w tygodniu i wybudowana zostanie autostrada między zabytkami a_i i b_i.

O ile każda autostrada łączy dwa różne zabytki, o tyle możliwe jest, że król Bajtazar w przypływie geniuszu zaplanował kilka autostrad łączących te same dwa zabytki.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą numer tygodnia, po którym można zorganizować wycieczkę w kółeczko. Jeśli taki tydzień nie istnieje (czyli po zbudowaniu wszystkich autostrad wciąż nie da się zorganizować wycieczki), program powinien wypisać jedno słowo "NIE" (bez cudzysłowów).

Przykład

Dla danych wejściowych:

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

prawidłową odpowiedzią jest:

5