다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 지도는 N x N 격자로 주어지며, 각 칸은 바다이거나 육지이다. 섬은 상하좌우로 이어진 육지 칸들의 한 덩어리이다.

서로 다른 두 섬을 하나의 다리로 연결하려고 한다. 다리는 바다 칸 위에만 놓을 수 있으며, 다리의 길이는 다리가 차지하는 격자 칸의 수이다.

주어진 지도에서 서로 다른 두 섬을 연결할 수 있는 가장 짧은 다리의 길이를 구하시오.

첫째 줄에 지도의 크기 N이 주어진다. N은 100 이하의 자연수이다.

다음 N개의 줄에는 지도를 나타내는 N개의 숫자가 공백으로 구분되어 주어진다. 0은 바다, 1은 육지를 뜻한다.

입력으로 주어지는 지도에는 항상 두 개 이상의 섬이 있다.

서로 다른 두 섬을 연결하는 가장 짧은 다리의 길이를 출력한다.