Pasy Ruchu

Limit pamięci: 64 MB

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

Bajtek, mieszkaniec miasta , nie lubi zbyt wiele razy kręcić kierownicą. Zastanawia się, jak dojechać do miasta , 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ć.

Wejście

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

Możesz założyć, że w testach wartych punktów zachodzi .

Wyjście

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.

Przykład

Dla danych wejściowych:

4 5
0 0 0 1 0
0 1 0 1 0
1 1 0 0 0
0 0 1 0 1

poprawną odpowiedzią jest:

2

Autor zadania: Jacek Tomasiewicz.