ВКОШП: ВКОШП 2019

Есть подозрение, что военный завод на окраине города причастен к серии недавних преступлений. Бюро общественной безопасности направило инспектора Акане выяснить, так ли это.

У Акане есть прямоугольная карта завода, являющаяся таблицей \(m \times n\). Каждая ячейка карты или является пустой, или содержит один из цехов завода. Разумеется, все цеха завода клеточно связаны, иначе говоря, от любого цеха до любого другого можно добраться через промежуточные цеха, переходя между цехами только по общей стороне. Также гарантируется, что завод не огораживает территорию, не являющуюся заводом, то есть от любой ячейки, не являющейся территорией завода, можно добраться до границы карты, переходя между ячейками, не являющимися цехами завода, по общей стороне.

Акане предполагает, что если на заводе и есть какие-то улики, то искать их в центре какого-либо цеха бесполезно. Гораздо вероятнее, что они находятся в углу цеха. Для упомянутой карты рассмотрим все узлы сетки, являющиеся углом хотя бы одного цеха. Акане называет такие узлы важными. Количество важных узлов, очевидно, не превосходит \((m + 1) \cdot (n + 1)\). Акане выяснила, что для каждой клетки с цехом, по её краям проложены коридоры, которые соединяют соседние узлы сетки, расположенные в углах этой клетки.

Акане хочет обойти все важные узлы, причём сделать это как можно более эффективно. А именно, Акане хочет составить маршрут по узлам сетки, такой что:

• маршрут начинается и заканчивается в одном и том же узле;
• между каждыми двумя узлами Акане переходит по коридорам;
• каждый важный узел посещается хотя бы один раз;
• маршрут проходит только по важным узлам;
• по каждому коридору Акане проходит не более одного раза.

Помогите Акане найти любой подходящий маршрут, или определите, что таковых не существует. Обратите внимание, что минимизировать длину маршрута не требуется.