Три штати#1061
На прямокутній карті розміром n \times m розташовані три штати. Гарантується, що у межах кожного штату можна дістатися з будь-якої клітини цього штату в будь-яку іншу клітину того ж штату, переміщаючись лише горизонтально або вертикально через клітини, що належать цьому штату. Клітини кожного штату позначені одним з чисел (1, 2 або 3).
На карті є прохідні клітини (.) та непрохідні клітини (#).
Потрібно прокласти дороги у мінімальній кількості прохідних клітин так, щоб стало можливо дістатися з будь-якої клітини одного штату до будь-якої клітини іншого штату. Усередині кожного штату можна пересуватися без обмежень. По карті можна пересуватися лише горизонтально або вертикально.
У першому рядку задано розмір карти та (1 \leq n, m \leq 1000). Кожен з наступних рядків містить по символів:
1, 2, 3 — клітини, що належать штатам;
. — прохідна клітина, тут можна будувати дорогу;
# — непрохідна клітина, тут не можна будувати дорогу.
Виведіть мінімальну кількість клітин, у яких потрібно побудувати дороги, щоб усі клітини всіх штатів стали з'єднаними. Якщо це неможливо — виведіть -1.
Приклад 1