Доктор Мосаддык хочет выкопать несколько нефтяных скважин в Персидском заливе. Залив представляет собой прямоугольное поле размера n × m. Каждая клетка либо содержит нефть, либо пуста.
Две клетки считаются соседними, если у них есть общая сторона. Путь — это такая последовательность клеток c1, c2, ..., cx, что каждая из них содержит нефть, и для каждого i: клетка ci имеет общую сторону с ci - 1 и ci + 1 (если они существуют). Две клетки называются соединенными, если между ними существует путь. Если выкопать скважину в определенной клетке, то можно добывать нефть из всех клеток, соединенных с данной. Выкапывать скважины в пустых клетках не разрешается.
Доктор Мосаддык также знает, что в Персидском заливе пустые клетки образуют целые ряды и строки. То есть если какая-то клетка пуста, то столбец и/или строка, содержащие ее, тоже пусты.
Помогите доктору Мосаддыку выяснить, сколько скважин нужно выкопать, чтобы выкачать всю нефть в заливе.
Выходные данные
Выведите одно число, минимальной количество скважин, которое должен выкопать доктор Мосаддык, чтобы выкачать всю нефть.
Это количество совпадает с количеством областей, на которые распадается прямоугольник после удаления всех пустых строк и столбцов.