Оптимальне розрізання#4649
У Полікарпа є прямокутна ґратка розміром n \times m, у кожній клітинці якої написана маленька латинська літера.
Дві клітинки називаються з'єднаними, якщо вони мають спільну сторону і в обох написана одна і та сама літера.
Монохромною областю називається група клітинок, таких що будь-які дві клітинки цієї групи з'єднані (безпосередньо або послідовністю інших клітинок), і неможливо додати до цієї групи ще жодної клітинки, не порушуючи цієї властивості.
Сторона клітинки називається внутрішньою, якщо вона розділяє дві різні клітинки ґратки.
Шляхом називається послідовність різних внутрішніх сторін, де кожна пара послідовних сторін перетинається у кутку якоїсь клітинки.
Полікарп хоче відділити всі монохромні області одну від одної, розрізаючи ґратку. Кожен розріз можна зробити вздовж шляху — тобто, він може проходити по послідовності ще нерозрізаних внутрішніх сторін, що утворюють шлях. Після всіх розрізів жодна монохромна область не повинна бути розділена.
Яку мінімальну кількість розрізів потрібно зробити Полікарпу, щоб досягти цього?
Перший рядок містить два цілі числа і (1 \leq n \times m \leq 10^5) — розміри ґратки.
Кожен з наступних рядків містить по маленьких латинських літер, що описують ґратку.
Виведіть одне ціле число — мінімальну кількість розрізів, необхідних для відокремлення всіх монохромних областей.
Приклад 1