산토끼

산토끼 바이텍(Bajtek)은 가로세로 $n \times m$ 미터 크기의 직사각형 풀밭에 산다. 이 풀밭은 한 변의 길이가 $1$미터인 정사각형 칸 $n \cdot m$개로 나뉘어 있다. 일부 칸에는 두더지가 쌓은 흙더미가 있는데, 바이텍은 항상 이 칸을 피한다.

바이텍의 한 번의 점프 거리는 정확히 $\sqrt{5}$이며, 바이텍은 지독한 완벽주의자라서 항상 칸의 정중앙에 착지하려 한다. 따라서 좌표 $(x, y)$인 칸에서 바이텍은 다음 좌표의 칸으로만 점프할 수 있다: $(x+1, y+2)$, $(x+1, y-2)$, $(x-1, y+2)$, $(x-1, y-2)$, $(x+2, y+1)$, $(x+2, y-1)$, $(x-2, y+1)$, $(x-2, y-1)$. 단, 풀밭 밖으로 벗어나는 점프는 할 수 없다.

바이텍은 두더지 흙더미가 있는 칸을 밟지 않으면서 가능한 한 빨리 자신의 굴에 도착하고 싶다. 바이텍이 서 있는 칸과 굴이 있는 칸이 주어질 때, 굴에 도착하기 위해 해야 하는 최소 점프 횟수를 구하여라.

표준 입력의 첫 번째 줄에는 공백 하나로 구분된 두 정수 $n$과 $m$이 주어진다 ($1 \le n, m \le 1000$, $n \cdot m \ge 2$). 이는 풀밭의 크기를 나타낸다. 이어지는 $n$개의 줄에는 각각 $m$개의 문자가 주어지며, 각 문자는 풀밭의 칸을 다음과 같이 나타낸다.

• "."는 빈 칸, 즉 바이텍이 뛰어들 수 있는 칸을 나타낸다.
• "x"는 두더지 흙더미가 있는 칸을 나타낸다.
• "z"는 현재 산토끼 바이텍이 서 있는 칸을 나타낸다.
• "n"은 바이텍의 굴이 있는 칸을 나타낸다.

정확히 한 칸만 "z"로, 정확히 한 칸만 "n"으로 표시된다고 가정해도 좋다.

표준 출력의 첫 번째이자 유일한 줄에, 바이텍이 굴에 도착하기 위해 해야 하는 최소 점프 횟수를 나타내는 하나의 양의 정수를 출력한다. 만약 올바른 점프만으로는 바이텍이 굴에 도착할 수 없다면 "NIE"를 출력한다.