Республиканская олимпиада по информатике 2014 года за 10 класс | Казахстанские олимпиады

Задача C. Максимальный квадрат

Ограничение по времени Ограничение по памяти
15 секунд 128 мегабайт

Дана матрица размера N×MN \times M состоящая только из нулей и единиц. Нужно найти наибольшую квадратную подматрицу, в сторонах которой только единицы.

Формат входного файла

Первая строка входного файла содержит два целых числа NN и MM. Следующие NN строк содержат по MM цифр 0 и 1, разделенных пробелом. Если таких квадратов нет, выведите 0.

Формат выходного файла

Выведите одно целое число -- размер максимального квадрата, в сторонах которого только единицы.

Примеры

Вход

4 5
01111
01011
11001
11111

Выход

4

Вход

2 3
000
000

Выход

0

Вход

3 3
011
011
010

Выход

2