Территория Берляндии представляет собой прямоугольное поле n × m клеток. Король Берляндии живет в столице, расположенной в верхней левой клетке (1, 1). Нижняя правая клетка имеет координаты (n, m). Однажды король решил объехать всю страну и вернуться назад в столицу, побывав в каждой клетке (кроме столицы) ровно один раз. В столице король должен побывать ровно два раза — в самом начале и в самом конце путешествия. Король может переходить только в соседние по стороне клетки. Однако королевский советник сказал, что, возможно, у короля не получится это сделать. Но есть выход — построить систему односторонних телепортов между некоторыми клетками так, чтобы король сумел осуществить задуманное. В одну клетку можно установить не более одного телепорта, каждый телепорт можно использовать сколько угодно раз, но при каждом использовании он ведет в одну и ту же, заранее заданную для каждого телепорта в отдельности клетку. Когда король приходит в клетку, где есть телепорт, он сам выбирает, будет ли он пользоваться телепортом. Какое наименьшее количество телепортов необходимо построить, чтобы король смог успешно совершить запланированное путешествие? Также требуется составить для короля маршрут путешествия.