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