Майкл обвиняется в нарушении масочного режима и создании риска распространения коронавируса. Теперь он приговорён отбывать наказание в тюрьме. К счастью, Майкл знает внутреннее устройство тюрьмы, а оно довольно простое.
Тюрьма может быть представлена в виде прямоугольника \(a\times b\), разбитого на \(ab\) клеток. Каждая клетка обозначает тюремную камеру, перегородки между клетками обозначают стены между камерами, и внешние перегородки обозначают внешние стены тюрьмы. Перед заключением Майкл может воспользоваться своими связями среди сотрудников тюрьмы, чтобы сделать (очень хорошо спрятанные) отверстия в стенах (как во внутренних, так и во внешних). Майкл не знает, в какую камеру он попадёт, но хочет, чтобы вне зависимости от этого он потом смог выбраться наружу. С другой стороны, чтобы обезопасить себя, он хочет сломать как можно меньше стен.
Найдите наименьшее количество стен, которые нужно сломать, чтобы после этого из каждой камеры можно было выбраться наружу.