홍수

해수면 상승 때문에 작은 섬나라 고나싱카는 걱정이 많다. 이들은 물이 얼마나 높이 차오르면 하나였던 섬이 두 개 이상의 섬으로 나뉘는지 알고 싶어 한다.

섬의 고도를 나타내는 정수 격자가 주어지며, 바다가 이 격자를 둘러싸고 있다. 바다가 높이 $f$ 피트까지 차오르면, 물은 바깥에서 안쪽으로 퍼진다. 어떤 칸은 그 고도가 $f$ 이하이고, 격자 바깥에서부터 고도가 모두 $f$ 이하인 칸들을 상하좌우로 인접하게 지나는 경로로 도달할 수 있을 때 물에 잠긴다. 더 높은 땅으로 완전히 둘러싸인 낮은 지역은 그 둘러싼 장벽이 넘칠 때까지 마른 상태로 남는다. 아직 물에 잠기지 않은(마른) 칸들이 서로 떨어진 두 개 이상의 연결된 조각을 이루게 되려면 바다가 얼마나 높이 차올라야 하는지 구하여라.

각 테스트 케이스는 두 양의 정수 $n$ 과 $m$(격자의 크기)이 적힌 줄로 시작하고, 이어서 $n$ 개의 줄에 각각 $m$ 개의 음이 아닌 정수(각 칸의 고도)가 주어진다. 두 칸은 상하좌우로 변을 맞댈 때에만 인접하며, 바다는 처음에 높이 $0$ 으로 격자를 둘러싸고 있다.

따라서 격자 가장자리에 있는 고도 $0$ 인 칸과, 다른 고도 $0$ 인 칸들을 통해 그것과 연결된 모든 고도 $0$ 인 칸은 이 초기 수위에서 바다이며, 가장자리와 연결되지 않은(더 높은 땅으로 둘러싸인) 고도 $0$ 인 칸은 해수면 높이의 마른 땅이다. 섬은 처음에 하나로 연결되어 있다. $n$ 과 $m$ 은 각각 $100$ 을 넘지 않으며, 어떤 고도도 $1000$ 을 넘지 않는다. 마지막 테스트 케이스 뒤에는 0 0 이 적힌 줄이 오며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 다음 두 줄 중 정확히 하나를 출력한다. 땅이 언젠가 나뉘는 경우에는

Case n: Island splits when ocean rises f feet.

를 출력하며, 여기서 n 은 ($1$ 부터 시작하는) 테스트 케이스 번호이고, f 는 땅을 두 개 이상의 조각으로 나누기 위해 바다가 차올라야 하는 가장 작은 정수 피트 값이다. 그렇지 않으면

Case n: Island never splits.

를 출력한다. 관례상 답이 $f$ 피트라는 것은 $f$ 피트에 아주 조금 더한 것을 뜻한다. 즉, 원래 높이가 $f$ 피트였던 땅 위로 적어도 아주 약간의 물이 흐르므로, 바다가 $f$ 피트에 이르면 고도 $f$ 인 칸은 잠긴 것으로 본다.