8687번 - Pasy Ruchu 다국어

Dawno temu w Bajtocji wybudowano autostradę o n pasach ruchu, łączącą dwa miasta A i B. Droga była jednak tak uczęszczana, że niektóre jej fragmenty stały się nieprzejezdne.

Bajtek, mieszkaniec miasta A, nie lubi zbyt wiele razy kręcić kierownicą. Zastanawia się, jak dojechać do miasta B, zmieniając pasy ruchu minimalną liczbę razy.

Bajtek może rozpocząć swoją podróż z dowolnego pasa ruchu i zakończyć również na dowolnym. Zgodnie z obowiązującymi zasadami ruchu drogowego na autostradzie nie wolno zawracać ani cofać.

Pierwszym wiersz standardowego wejścia zawiera dwie liczby całkowite n i m (1 ≤ n, m ≤ 1 000). W n następnych wierszach znajdują się opisy kolejnych pasów ruchu. Każdy z takich wierszy zawiera m liczb całkowitych: 0 to przejezdny fragment autostrady, natomiast 1 to nieprzejezdny.

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą minimalnej liczbie zmian pasów ruchu, lub jedno słowo NIE, jeśli przejazd przez autostradę jest niemożliwy.