Блокада

Flatlandia — це прямокутна країна, що складається з одиничних квадратів. Flatlandia поділена на $K$ провінцій (2 \leq K \leq 100). Кожна провінція — це зв'язана множина квадратів, тобто з будь-якої клітини провінції можна дістатися до будь-якої іншої клітини цієї ж провінції, переходячи лише між клітинами із спільною стороною (спільних вершин недостатньо). У Flatlandia немає точки, у якій чотири провінції зустрічаються в одній вершині (тобто чотири квадрати, які мають спільну вершину, не належать до чотирьох різних провінцій).

Кожна провінція позначена унікальним символом. Столиця Flatlandia знаходиться у провінції, що позначена символом A (велика літера A). Провінція називається прикордонною, якщо вона містить хоча б одну клітину на межі карти. Провінція зі столицею (символ A) не є прикордонною.

Король сусіднього королівства Rectilania бажає завоювати Flatlandia. Для цього він планує захопити столицю Flatlandia. Однак його армія недостатньо сильна, щоб захопити її безпосередньо. Тому спочатку він хоче оточити провінцію-столицю, щоб послабити ворога тривалою блокадою, а вже потім захопити столицю.

Щоб оточити провінцію, потрібно захопити всі провінції, що з нею межують. Дві провінції вважаються сусідніми (такими, що межують), якщо існують дві клітини, які мають спільну сторону, одна з яких належить до першої провінції, а інша — до другої. Щоб захопити провінцію, повинна виконуватись одна з двох умов: провінція є прикордонною, або вона межує з будь-якою провінцією, яку вже було захоплено.

Король хоче захопити якнайменше провінцій, щоб встановити блокаду. Захоплювати столичну провінцію не дозволено, адже сили армії для цього ще недостатньо.