eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

У Полікарпа є прямокутний шматочок клітчатого паперу n×m клітинок. У кожній клітинці аркушу записано літеру.

Дві клітинки назвемо зв'язними, якщо вони мают спільну сторону і в них записано одну й ту ж літеру.

Однокольоровою областю назвемо множиу клітинок паперу таких, що довільні дві клітинки цієї множини зв'язані напряму або побічно (через послідовність інших клітинок) і при цьому не можна збільшувати цю множину, не порушуючи попередньої властивості.

Сторона клітинки називається внутрішньою, якщо вона відокремлює одну від одної дві якісь клітинки паперу.

Шляхом назвемо послідовність різних внутрішніх сторін клітинок паперу таку, що довільні дві послідовні сторони перетинаються у куті якоїсь клітинки.

Полікарп хоче від'єднати усі однокольорові області одну від одної, розрізаючи папір. Одним розрізом дозволяється розрізати послідовність раніше не розрізаних сторін, яка утворює деякий шлях. Яку мінімальну кількість розрізів йому для цього знадобиться? Врахуйте, что після застосування розрізів однокольорові області не повинні опинитись розрізаними.

Вхідні дані

У першому рядку записано два цілих числа через пропуск n та m (1 ≤ n×m10^5) — розміри шматочка паперу.

У наступних n рядках записано по m рядкових літер латинського алфавіту — опис шматочка паперу.

Вихідні дані

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

Приклад

Вхідні дані #1
2 2
ab
ba
Вихідні дані #1
2
Джерело Зимова школа Харків 2013, День 6 - Г.Агапова та І.Фефера