Blokada
Düzbucaqlı ölçüdə olan Flatlandiya dövləti, vahid kvadratçıklardan ibarətdir. Flatlandiya K əyalətə (2 ≤ K ≤ 100) bölünmüşdür. Hər bir əyalət əlaqəli kvadratçıklar toplusudur, yəni əyalətin hər nöqtəsindən digər nöqtəsinə keçmək mümkündür, yalnız kvadratçıklar ortaq tərəfə malik olduqda keçid icazəlidir (ortaq zirvə kifayət deyil). Flatlandiyada dörd fərqli əyalətə aid olan ortaq zirvəyə malik dörd kvadratçık yoxdur.
Hər bir əyalətin öz simvolu var. Flatlandiyanın paytaxtı A simvoluna (böyük latın hərfi A) aid olan əyalətdə yerləşir. Əyalət sərhəd kvadratçıkları ehtiva edirsə, sərhəd əyaləti adlanır. Flatlandiyanın paytaxtının yerləşdiyi əyalət sərhəd əyaləti deyil.
Flatlandiyanın qonşusu olan Rektlaniya krallığının kralı Flatlandiyanı fəth etmək qərarına gəlib. Bunun üçün o, Flatlandiyanın paytaxtını ələ keçirmək istəyir. Lakin, ordusunun gücü bunu dərhal etmək üçün kifayət deyil. Buna görə də, əvvəlcə paytaxt əyalətini mühasirəyə alaraq düşmənin gücünü uzun müddətli blokada ilə zəiflətmək, sonra isə paytaxtı ələ keçirmək istəyir.
Əyaləti mühasirəyə almaq üçün onunla sərhəd olan bütün əyalətləri ələ keçirmək lazımdır. İki əyalət sərhəd sayılır, əgər ortaq tərəfə malik olan iki kvadratçık varsa, bunlardan biri birinciyə, digəri isə ikinciyə aiddir. Əyaləti ələ keçirmək üçün iki şərtdən biri yerinə yetirilməlidir: ya o sərhəd əyalətidir, ya da artıq ələ keçirilmiş əyalətlə sərhəd olmalıdır.
Rektlaniya kralı ordusunun gücünü qorumaq üçün mümkün qədər az əyalət ələ keçirərək paytaxt əyalətini mühasirəyə almaq istəyir. Ona neçə əyalət ələ keçirmək lazım olduğunu müəyyənləşdirməkdə kömək edin. Paytaxt əyalətini ələ keçirmək olmaz, çünki Rektlaniya ordusunun gücü hələlik buna kifayət deyil.
Giriş verilənləri
Birinci sətir M və N (3 ≤ M, N ≤ 200) ehtiva edir. Növbəti M sətir hər biri N simvol ehtiva edir və Flatlandiyanın xəritəsini təsvir edir. Giriş faylının i+1-ci sətirində j-ci yerdə olan simvol, kvadratçığın (i, j) aid olduğu əyalətin simvolunu göstərir. Bütün simvolların ASCII-kodu 32-dən böyükdür (boşluq).
Çıxış verilənləri
Çıxış faylında tək bir ədəd - ələ keçirilməsi lazım olan əyalətlərin sayını göstərin. Əgər blokada qurmaq mümkün deyilsə, "–1" çıxarın.