Optimal Cutting
Polycarp has a rectangular grid of paper with dimensions n×m, where each cell contains a letter.
Two cells are considered connected if they share a side and have the same letter.
A monochromatic region is a group of cells where any two cells are connected directly or indirectly (through a chain of other cells), and this group cannot be expanded without losing this property.
A cell's side is called internal if it separates two cells on the paper.
A path is a sequence of distinct internal sides such that each pair of consecutive sides meets at a cell corner.
Polycarp wants to separate all monochromatic regions by cutting the paper. Each cut can slice through a sequence of previously uncut sides that form a path. What is the minimum number of cuts needed to achieve this? Note that the cuts should not divide any monochromatic region.
Input
The first line contains two integers n and m (1 ≤ n×m ≤ 10^5) — the dimensions of the grid.
The next n lines each contain m lowercase Latin letters, representing the grid.
Output
Output a single integer — the minimum number of cuts required to separate the monochromatic regions.