Острови#3062
Генератор випадкових карт у популярній грі Heroes of Might and Magic III створює острови, на яких спочатку розміщуються герої. Ці острови можуть мати різний розмір. Ми визначаємо відношення площі найбільшого острова до площі найменшого як коефіцієнт диспропорції. Ваше завдання — обчислити цей коефіцієнт.
Карта подається у вигляді прямокутника розміром N \times M, де кожна клітинка містить або цифру (означає воду), або (означає сушу). Острів визначається як максимальна зв’язкова група клітинок, що містять одиниці, тобто група така, що:
З будь-якої клітинки з можна дістатися до будь-якої іншої клітинки з , переходячи лише через суміжні клітинки з (що мають спільну сторону).
Додавання будь-якої іншої клітинки з до порушить цю умову зв’язковості.
У першому рядку вхідних даних задано числа та (1 \leq N, M \leq 1000), які є розмірами карти. Далі подається сама карта, що складається з рядків, у кожному міститься чисел ( або ), розділених пробілами.
Виведіть коефіцієнт диспропорції, відформатований до знаків після коми. Якщо на карті немає жодного острова, виведіть 0.
Приклад 1