Ханойская башня

Есть три стержня ($1$, $2$, $3$). На стержне $a$ лежат $n$ дисков: внизу самый большой, выше — всё меньше. Нужно перенести все диски на стержень $b$. Правила: за ход берётся только один диск — верхний с какого-либо стержня — и кладётся на другой; больший диск нельзя класть на меньший.

Перенесите диски за наименьшее число ходов и выведите ходы по порядку.

В одной строке $n$, $a$, $b$ ($1 \le n \le 10$; $a, b \in \{1, 2, 3\}$, $a \ne b$).

В первой строке число ходов. Затем каждый ход в отдельной строке: номер стержня, откуда берём, и куда кладём.

Чтобы перенести $n$ дисков с $a$ на $b$: перенесите верхние $n - 1$ дисков на третий стержень ($6 - a - b$), положите самый большой на $b$, затем перенесите $n - 1$ дисков с третьего стержня на $b$. Базовый случай: $n = 0$ — ничего не делаем. Ходов $2^n - 1$, а последовательность с наименьшим числом ходов единственна.

Первый пример: малый диск $1 \to 2$, большой $1 \to 3$, малый $2 \to 3$.