Потоп
Глобальне потепління змушує нас замислитися про підняття рівня океанів — особливо тих, хто живе поблизу узбережжя. Маленька острівна держава Гоннасінка звернулася до вас із проханням відповісти на кілька запитань. Зокрема, їх цікавить, наскільки має піднятися рівень води, щоб їхній острів розділився на два або більше окремих островів.
Вам надано сітку цілих чисел, що представляють висоти острова. Ваше завдання — визначити, наскільки має піднятися океан, щоб земля розділилася на частини.
Вхідні дані
Кожен тестовий випадок починається з рядка, що містить два додатні цілі числа n, m, які визначають розміри сітки. Далі йдуть n рядків, кожен з яких містить m додатних цілих чисел, що вказують початкову висоту елементів сітки. Елементи сітки вважаються суміжними, якщо вони мають спільну горизонтальну або вертикальну грань. Значення нуля (0) по периметру, а всі нульові клітинки, з'єднані з ними, є океаном на початковому рівні. Клітинки з 0, не з'єднані з периметром (тобто оточені вищою землею), є просто висотами на рівні моря. Крім того, припускається, що океан спочатку оточує дану сітку. Острів спочатку є цілісним. Ні n, ні m не перевищують 100, а висоти ніколи не перевищують 1000. Рядок з 0 0 слідує за останнім тестовим випадком.
Вихідні дані
Для кожного тестового випадку виведіть один з двох наступних рядків.
Випадок n: Острів розділиться, коли океан підніметься на f футів.
або
Випадок n: Острів ніколи не розділиться.
Наша конвенція полягає в тому, що якщо ваша відповідь, наприклад, 5 футів, ви маєте на увазі "5 футів плюс трохи більше." Тобто, принаймні трохи води буде текти над початково 5-футовою висотою землі.