The Flood

Rising oceans have the small island nation of Gonnasinka worried: they want to know how high the water must rise before their single island becomes two or more islands.

You are given a grid of integers giving the altitudes of the island, and the ocean surrounds the grid. As the ocean rises to a level of $f$ feet, water spreads inward from outside: a cell becomes submerged if its altitude is at most $f$ and it can be reached from outside the grid through a path of horizontally or vertically adjacent cells each having altitude at most $f$. A low area that is completely enclosed by higher land stays dry until that surrounding barrier is overtopped. Determine how high the ocean must rise before the cells that are still dry form two or more separate connected pieces.

Each test case begins with a line containing two positive integers $n$ and $m$, the dimensions of the grid, followed by $n$ lines each containing $m$ non-negative integers, the altitudes of the cells. Two cells are adjacent only when they share a horizontal or vertical edge, and the ocean initially surrounds the grid at level $0$.

Consequently, a cell of altitude $0$ on the perimeter, together with every altitude-$0$ cell connected to it through other altitude-$0$ cells, is ocean at this initial level, while an altitude-$0$ cell not connected to the perimeter (enclosed by higher land) is dry land at sea level. The island is initially a single connected piece. Neither $n$ nor $m$ exceeds $100$, and no altitude exceeds $1000$. A line containing 0 0 follows the last test case and is not processed.

For each test case, output exactly one of the following two lines. If the land eventually splits, output

Case n: Island splits when ocean rises f feet.

where n is the test case number (starting from $1$) and f is the smallest whole number of feet the ocean must rise to break the land into two or more pieces. Otherwise output

Case n: Island never splits.

By convention, an answer of $f$ feet means $f$ feet plus a little more: at least a little water flows over the land that was originally $f$ feet high, so a cell of altitude $f$ counts as submerged once the ocean reaches $f$ feet.