Traffic Lanes

Long ago, a highway with $n$ lanes was built in Bytocia (Bajtocja), connecting the two cities $A$ and $B$. The road became so heavily travelled that some of its fragments turned impassable.

Bajtek, a resident of city $A$, does not like turning the steering wheel too many times. He wonders how to reach city $B$ while changing lanes as few times as possible.

Bajtek may start his journey from any lane and may also finish on any lane. Under the highway traffic rules, making a U-turn or reversing is not allowed.

The first line of standard input contains two integers $n$ and $m$ ($1 \le n, m \le 1000$). Each of the next $n$ lines describes one lane, in order. Each such line contains $m$ integers: 0 marks a passable fragment of the highway and 1 marks an impassable one.

Print a single integer, the minimum number of lane changes, on the first and only line of standard output. If crossing the highway is impossible, print the single word NIE instead.