Максимальний квадрат#7837

Максимальний квадрат

1 секунда
122,174 мегабайта
Складна

Дано матрицю розміру n \times m, що складається лише з нулів і одиниць. Потрібно знайти найбільшу квадратну підматрицю, у якої всі елементи на сторонах є одиницями.

Вхідні дані

Перший рядок містить два цілі числа і (1 \le n, m \le 1500). Наступні рядків містять по цифр і , розділених пробілом.

Вихідні дані

Виведіть одне ціле число — розмір найбільшого квадрата, на сторонах якого лише одиниці. Якщо таких квадратів немає, виведіть .

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading