Некоторая тропическая республика представляет собой архипелаг, состоящий из нескольких (не менее двух) островов. Карта архипелага представляет собой матрицу $$$n \times m$$$, в которой символ '1' означает землю, а цифра '0' — воду. Любые две соседние по стороне клетки с символом '1' принадлежат одному острову.
Свежеизбранный президент республики в ходе предвыборной гонки обещал соединить все острова мостами. Теперь обещание нужно выполнять, но денег в стране немного. Поэтому он решил начать с возведения самого маленького моста. Определите, какое наименьшее число клеток нужно изменить с '0' на '1', чтобы какие-нибудь два острова (или более) соединились.
В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1\le n, m \le 10^6$$$, $$$n \cdot m \le 10^6$$$).
В следующих $$$n$$$ строках записано по $$$m$$$ символов '0' или '1' без пробелов. Гарантируется, что в матрице имеется не менее двух связных по стороне областей из единичных клеток.
Выведите одно целое число — ответ.
3 3 101 010 101
1
2 3 100 001
2
