Sections > Unsorted > problem:

Ханойские башни

Section problems

• Умножение матриц
• Умножение матриц
• Уравнение
• Уравнение
• Условия (подсказки к задачам)
• Факторизация
• Ферма
• Функции (подсказки к задачам)
• Ханойские башни
• Хилла
• Хорошая погода
• Цезарь
• 1
• Цикл
• Циклы (подсказки к задачам)
• Четвертьфинал
• Четвертьфинал

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 65536/65536/65536/65536 Kb.

Ханойские башни

Головоломка «Ханойские башни» представляет собой три стержня. На стержень #1 нанизана пирамида из N дисков увеличивающегося диаметра.

$\text{[math]}$

Требуется перенести пирамиду со стержня #1 на стержень #3, пользуясь стержнем #2 как вспомогательным. При этом следует придерживаться следующих правил:

За один ход разрешается перенести верхний диск с одного стержня на другой;
Диск большего диаметра нельзя класть на диск меньшего диаметра.

Выведите инструкцию по решению головоломки за наименьшее число ходов.

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

Ввод содержит целое число N (1 ≤ N ≤ 20) — количество дисков на стержне #1.

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

Выведите одну или более строк вида X Y (1 ≤ X, Y ≤ 3) — «перенести верхний диск со стержня #X на стержень #Y», позволяющих решить головоломку в соответствии с правилами. Количество строк в выводе должно быть минимально возможным.

Примеры

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

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

1 2
1 3
2 3

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

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

Для отправки решений необходимо выполнить вход.