AlgoLiga 2018

Bitazar kontynuuje swoją przygodę z rozwożeniem pizzy. Jego interes kwitnie, jednak jeszcze nie dorobił się wielu pracowników. To się już niedługo zmieni, ale póki co ma spore zamówienie do zrealizowania w jednej z dzielnic Bitlandii. Dzielnica ta nazywa się dzielnicą Pełną i jest bardzo specyficzna. Składa się ona z n domów, ponumerowanych kolejno liczbami naturalnymi od 1 do n, z których każde dwa połączone są jednokierunkową ulicą. Bitazar ma pełne ręce roboty, bowiem wszyscy mieszkańcy dzielnicy Pełnej złożyli zamówienie, a on ma do dyspozycji jedynie swój dzielny skuter.

Tym razem jest o tyle lepiej, że zamówienia może zrealizować w dowolnej kolejności, ponieważ mieszkańcy mają pełno czasu. Chciałby je zrealizować w ciągu, jedno za drugim, odwiedzając w każdym kolejnym kroku dom, do którego jeszcze pizzy nie dostarczył. Aby jednak nie pogubić się w gęstej sieci ulic dzielnicy Pełnej poprosił Cię o wyznaczenie mu trasy.

Wejście

Wejście rozpoczyna liczba 1 < n ≤ 2000 oznaczająca liczbę domów w dzielnicy Pełnej. Następnie jest n wierszy po n liczb ze zbioru {0,1} każda. W i-tym wierszu oraz j-tej kolumnie znajduje się liczba 1 wtedy i tylko wtedy gdy domy o tych numerach połączone są ulicą w kierunku od i-tego domu do j-tego.

Wyjście

Na wyjście należy wypisać ciąg n różnych numerów domów oddzielonych spacjami - kolejność w jakiej Bitazar ma realizować zamówienia. Bitazar przestrzega zasad ruchu drogowego, więc każde kolejne dwa domy w tym ciągu muszą być połączone ulicą w kierunku od pierwszego do drugiego domu. Jeśli rozwiązanie nie istnieje należy wypisać jedno słowo "NIE" (bez cudzysłowu). Jeśli istnieje wiele rozwiązań należy wypisać dowolne z nich.

Przykład

Wejście:
5
0 0 0 1 0 
1 0 1 0 0 
1 0 0 1 1 
0 1 0 0 0 
1 1 0 1 0

Przykładowe wyjście:
3 5 2 1 4