Blokada

Flatlandiya vahid kvadratlardan ibarət düzbucaqlı bir ölkədir. Flatlandiya $K$ vilayətə bölünüb (2 \leq K \leq 100). Hər bir vilayət əlaqəli xanalar toplusudur, yəni vilayətin istənilən xanadan digər xanasına yalnız ümumi tərəfi olan xanalardan keçməklə çatmaq mümkündür (yalnız ümumi zirvə kifayət deyil). Flatlandiyada dörd vilayətin bir zirvədə (xananın küncündə) görüşdüyü heç bir nöqtə yoxdur (yəni, dörd xananın paylaşdığı bir zirvə dörd müxtəlif vilayətə mənsub ola bilməz).

Hər bir vilayət özünəməxsus simvolla göstərilir. Flatlandiyanın paytaxtı $\text{A}$ simvolu (böyük $\text{A}$ hərfi) ilə göstərilən vilayətdə yerləşir. Vilayət sərhəd vilayət adlanırsa, o, xəritənin sərhədində ən azı bir xana saxlayır. Paytaxtın yerləşdiyi vilayət ($\text{A}$ simvollu) sərhəd vilayət deyil.

Qonşu dövlət Rectilaniyanın kralı Flatlandiyanı fəth etmək istəyir. Bunun üçün o, Flatlandiyanın paytaxtını ələ keçirmək niyyətindədir. Lakin onun ordusu bunu birbaşa etmək üçün kifayət qədər güclü deyil. Buna görə də, əvvəlcə paytaxt vilayətini mühasirəyə almaq, uzunmüddətli blokada ilə düşməni zəiflətmək və yalnız bundan sonra paytaxtı ələ keçirmək istəyir.

Bir vilayəti mühasirəyə almaq üçün ona sərhəddə olan bütün vilayətlər ələ keçirilməlidir. İki vilayət qonşu (sərhəd) sayılırsa, onların iki xanası ümumi tərəfləri ilə qonşudursa və bu xanalardan biri birinci, digəri ikinci vilayətə məxsusdursa. Bir vilayəti ələ keçirmək üçün iki şərtdən biri ödənilməlidir: ya o, sərhəd vilayətidir, ya da ələ keçirilmiş hər hansı başqa vilayətə qonşudur.

Kral mümkün qədər az sayda vilayət ələ keçirərək blokada yaratmaq istəyir. Paytaxt vilayətini (ordu hələ kifayət qədər güclü olmadığı üçün) ələ keçirmək olmaz.