AlgoLiga 2018

Jaś wstąpił w szeregi przestępców. Jego cel, to obrabowanie banku rezerw. Bank to bardzo wielki i bardzo dobrze zabezpieczony budynek. Plan naszego złodzieja obejmuje: wejście do banku, wyłączenie zabezpieczeń, zdemontowanie monitoringu, wjechanie ciężarówkami po złoto oraz niezauważalną ucieczkę. Wydaje się, że plan jest perfekcyjny i już wszystko jest idealnie zaplanowane (bo tak jest), jednak została ostatnia kwestia do rozwiązania - złamanie szyfrów do sejfów. Każdy z nich trzeba osobno otwierać, lecz trzeba to zrobić szybko, gdyż w przeciwnym wypadku cały plan okaże się fiaskiem. Jaś, jak widać, bardzo dobrze radzi sobie w branży i również wpadł na pomysł, jak to załatwić. Wie, że każdy zamek ma N przesuwek, a każda z nich może być ustawiona na 2 pozycjach, jakie posiada (pozycje i-tej przesuwki to a_i i b_i; 1 ≤ a_i,b_i ≤ N). Zamek otwiera takie ustawienie, w którym powstały ciąg jest jak najmniejszy leksykograficznie, a zarazem każda liczba od 1 do N pojawia się dokładnie raz na którejś pozycji.

Twoim zadaniem jest napisanie dla Jasia programu, który wygeneruje odpowiednie numery, a w nagrodę, kto wie, może dostaniesz jedną ze złotych sztabek...?

Wejście:

W pierwszej linii liczba N,  oznaczająca liczbę przesuwek.

W kolejnych N liniach pojawiają się dwie liczby a_i i b_i - oznaczające parę numerów na i-tej przesuwce

Ograniczenia: 1 ≤ N ≤ 500 000;  1 ≤ a_i,b_i ≤ N;

Wyjście:

Należy wypisać N różnych liczb w jednej linii (oddzielonych spacjami) oznaczających kody, które otwierają zamek (i-ta liczba musi być równa a_i lub b_i). Jeśli zaś nie jest możliwe ułożenie ciągu, który spełnia warunki zadania, należy wypisać „NIE”, co oznacza, że sejf działa na innej zasadzie i Jaś nie będzie w stanie go otworzyć.

Przykład 1:

Wejście:
4
3 2
2 1
2 4
4 1

Wyjście:
3 1 2 4

Przykład 2:

Wejście:
3
3 3
2 1
3 3

Wyjście:
NIE