25585번 - 86 ─에이티식스─ 1

산마그놀리아 공화국은 '레기온'이라는 인공지능 무인 병기들과 전쟁 중이다. 공화국은 레기온에 대항할 수단으로 '저거노트'라는 보행 병기를 개발했다. 공화국 군인들은 이 저거노트에 탑승해서 레기온에 맞서 싸운다.

신에이 노우젠은 동부전선 제1전대의 전대장이자 근접전의 대가이다. 그는 레기온들의 위치를 전부 파악할 수 있는 이능력이 있다. 그의 전투 스타일은 직접 레기온이 있는 위치로 도약해서 빠르게 해치우는 것이다. 저거노트는 화력이 다소 약하지만, 기동성이 뛰어나다는 장점이 있기 때문이다.

저거노트는 대각선 네 방향으로 이동할 수 있다. 현재 좌표가 $(r,\,c)$ 라면 $(r - 1,\,c - 1)$, $(r - 1,\,c + 1)$, $(r + 1,\,c - 1)$, $(r + 1,\,c + 1)$로 움직일 수 있다.

<저거노트 이동 가능 좌표>

저거노트가 한 번 이동하는 데는 1초 걸린다. 신에이 노우젠은 레기온이 있는 위치로 직접 이동해서 레기온을 해치우는데, 전투에 매우 뛰어나서 레기온이 있는 위치로 도약하기만 하면 바로 레기온을 해치울 수 있다. 즉, 레기온을 해치우는 데 걸리는 시간은 0이다.

기습받은 레기온들은 당황하여 모두 움직임을 멈춘 상태다. 레기온들의 위치가 주어졌을 때, 신에이 노우젠이 레기온을 모두 해치우는 게 가능한지 여부, 그리고 가능하다면 모두 해치우는데 걸리는 최소 시간을 계산해보자.

신에이 노우젠은 전장을 벗어나 이동할 수는 없다.

첫 번째 줄에 전장의 크기 $N$이 주어진다. 전장은 $N \times N$ 크기 좌표로 이루어져 있다. 다음 $N$개의 줄에는 전장의 정보가 주어진다. 각 줄마다 $N$개의 좌표 정보가 주어지며 0은 빈칸, 1은 레기온, 2는 신에이 노우젠의 현재 위치를 나타낸다.

레기온 개수는 아무리 많아도 10개를 넘기지 않는다.

• $1 \leq N \leq 100$
• $0 \leq$ 레기온 개수 $\leq \min(N^2-1,\,10)$
• 신에이 노우젠의 위치는 유일하다.

전장에 레기온이 없거나 모든 레기온을 해치울 수 있다면 첫 줄에 "Undertaker" 를 출력하고 둘째 줄에 레기온을 모두 해치우는데 걸리는 최소 시간을 초 단위로 출력한다. 모든 레기온을 해치울 수 없다면 "Shorei" 를 출력한다.