Ханой минораси

Учта қозиқ ($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$.