쉬운 최단거리

지도가 주어진다. 모든 칸에서 목표 지점까지의 최단 거리를 구하여라.

문제를 쉽게 만들기 위해 이동은 상하좌우 네 방향으로만 할 수 있다고 하자. 인접한 칸으로 한 번 움직이면 거리가 1 늘어나고, 갈 수 없는 땅은 지나갈 수 없다.

첫째 줄에 지도의 크기 $n$과 $m$이 주어진다. $n$은 세로 크기, $m$은 가로 크기다. ($2 \le n \le 1000$, $2 \le m \le 1000$)

다음 $n$개 줄에 각각 $m$개의 숫자가 공백으로 구분되어 주어진다. 0은 갈 수 없는 땅, 1은 갈 수 있는 땅, 2는 목표 지점이다. 2는 입력 전체에 정확히 한 개 있다.

$n$개 줄에 각각 $m$개의 수를 공백으로 구분해 출력한다. $r$번째 줄의 $c$번째 수는 $r$행 $c$열 칸에서 목표 지점까지의 최단 거리다.

갈 수 없는 땅인 칸은 0을 출력한다. 갈 수 있는 땅이지만 목표 지점에 도달할 수 없는 칸은 -1을 출력한다. 목표 지점 자체는 0을 출력한다.