차선

옛날 옛적, 바이토시아(Bajtocja)에 두 도시 $A$와 $B$를 잇는 $n$개의 차선으로 이루어진 고속도로가 건설되었다. 그런데 이 도로는 이용량이 너무 많은 나머지 일부 구간이 통행할 수 없게 되어 버렸다.

도시 $A$에 사는 바이텍(Bajtek)은 운전대를 여러 번 돌리는 것을 좋아하지 않는다. 그는 차선을 최소한의 횟수만 바꾸면서 도시 $B$에 도착하는 방법을 고민하고 있다.

바이텍은 어느 차선에서든 출발할 수 있고, 어느 차선에서든 도착할 수 있다. 고속도로의 교통 규칙상 유턴이나 후진은 할 수 없다.

표준 입력의 첫째 줄에는 두 정수 $n$과 $m$이 주어진다 ($1 \le n, m \le 1000$). 이어지는 $n$개의 줄에는 각 차선의 정보가 순서대로 주어진다. 각 줄에는 $m$개의 정수가 주어지며, 0은 통행할 수 있는 구간을, 1은 통행할 수 없는 구간을 의미한다.

표준 출력의 첫째 줄에 차선을 바꾸는 최소 횟수를 나타내는 정수 하나를 출력한다. 만약 고속도로를 통과하는 것이 불가능하다면 대신 NIE라는 한 단어를 출력한다.