Üç dövlət
Üç dövlət n * m ölçüsündə düzbucaqlı xəritədə yerləşir. Hər hansı bir dövlətin istənilən hüceyrəsindən həmin dövlətin istənilən digər hüceyrəsinə yalnız üfüqi və ya şaquli hərəkətlə çatmaq mümkündür. Hər bir dövlətin hüceyrələri bir rəqəmlə (1, 2 və ya 3) işarələnmişdir.
Xəritədə keçilə bilən (".") və keçilməz ("#") hüceyrələr mövcuddur.
Elə yollar qurun ki, keçilə bilən hüceyrələrin ən az sayında bir dövlətdən digərinə keçmək mümkün olsun. Hər hansı bir dövlətin hüceyrələrində maneəsiz hərəkət etmək mümkündür. Xəritədə yalnız üfüqi və şaquli hərəkət etmək mümkündür.
Giriş məlumatları
Birinci sətir xəritənin ölçüsünü n və m (1 ≤ n, m ≤ 1000) verir. Növbəti n sətir m simvolu ehtiva edir:
1, 2, 3 - dövlətlərə aid hüceyrələr;
"." - keçilə bilən hüceyrə, burada yol qurmaq olar;
"#" - keçilməz hüceyrə, burada yol qurmaq olmaz;
Çıxış məlumatları
Bütün dövlətlərin bütün hüceyrələrinin birləşdirilməsi üçün yol qurulması lazım olan ən az hüceyrə sayını çıxarın. Əgər bunu etmək mümkün deyilsə, -1 çıxarın.