Problem description
Za górami, za lasami, w odległym Tybecie buddyjscy mnisi zajmują się sprawami, które wpływają na bieg wszechrzeczy. Głównym obiektem ich zainteresowania są złote krążki nanizane na diamentowe pręty.
Mamy trzy pręty i N krążków różnych rozmiarów nanizanych na pierwszy pręt. Krążki są ułożone od największego do najmniejszego (patrząc od dołu do góry).
Chcemy przenieść wszystkie krążki z pierwszego pręta na drugi, być może używając trzeciego i przestrzegając następujących reguł:
- w pojedynczym ruchu można przełożyć tylko jeden krążek;
- nigdy nie kładziemy większego krążka na mniejszy.
Napisz program, który dla danego N wyznaczy najkrótszą sekwencję ruchów, która prowadzi do rozwiązania powyższego problemu.
Wejście
W pierwszym wierszu wejścia znajdują się liczba naturalna N oznaczająca liczbę krążków, które chcemy przenieść.
Wyjście
Na wyjściu powinna zostać wypisana najkrótsza sekwencja ruchów prowadząca do przeniesienia krążków z pierwszego pręta na drugi. W i-tym wierszu powinny znaleźć się dwie liczby ai, bi oddzielone spacją, oznaczające, że w i-tym ruchu przekładamy krążek z pręta ai na pręt bi.
Ograniczenia
1 ≤ N ≤ 20.
Przykład
| Wejście | Wyjście | |
|
|