Задача №3809. Ремонт в Ханое

Задачи на рекурсию

Постановлением ЮНЕСКО оригинал Ханойской башни был подвергнут реставрации. В связи с этим во время пользования головоломкой нельзя было перекладывать кольца с первого стержня сразу на третий и наоборот.

Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.

Входные данные

Вводится натуральное число - количество колец.

Выходные данные

Выведите ответ на задачу.

Примеры
Входные данные
2
Выходные данные
1 1 2
1 2 3
2 1 2
1 3 2
1 2 1
2 2 3
1 1 2
1 2 3
Сдать: для сдачи задач необходимо войти в систему