eolymp
bolt
Try our new interface for solving problems
Problems

Оптимальное разрезание

Оптимальное разрезание

Time limit 1 second
Memory limit 256 MiB

У Поликарпа есть прямоугольный кусочек клетчатой бумаги n×m клеток. В каждой клетке бумаги записана буква.

Две клетки назовём связными, если они имеют общую сторону и в них записана одна и та же буква.

Одноцветной областью назовем множество клеток бумаги таких, что любые две клетки этого множества связаны напрямую или косвенно (через последовательность других клеток) и при этом нельзя увеличить это множество, не нарушая предыдущего свойства.

Сторона клетки называется внутренней, если она отделяет друг от друга две какие-то клетки бумаги.

Путём назовем последовательность различных внутренних сторон клеток бумаги такую, что любые две последовательные стороны пересекаются в углу какой-то клетки.

Поликарп хочет отсоединить все одноцветные области друг от друга, разрезая бумагу. Одним разрезом разрешается разрезать последовательность ранее не разрезанных сторон, образующую некоторый путь. Какое минимальное количество разрезов ему для этого понадобится? Учтите, что после применения разрезов одноцветные области не должны оказаться разрезанными.

Input data

В первой строке записано два целых числа через пробел n и m (1 ≤ n×m10^5) — размеры кусочка бумаги.

В следующих n строках записано по m строчных букв латинского алфавита — описание кусочка бумаги.

Output data

Выведите единственное целое число — минимальное количество разрезов, требуемое для отделения цветных областей друг от друга.

Examples

Input example #1
2 2
ab
ba
Output example #1
2
Source Winter School Kharkov 2013, Day 6 - G.Agapov and I.Fefer