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.
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.
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).
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
[Zgłoś rozwiązanie] [Moje zgłoszenia]