10089 하노이의 탑 Silver III

문제

하노이의 탑 문제이다. 세 개의 장대가 있고, 첫 번째 장대에 N개의 원판이 크기 순으로 쌓여 있다. 모든 원판을 세 번째 장대로 옮기는 과정을 출력하시오.

규칙: 한 번에 하나의 원판만 옮길 수 있고, 큰 원판 위에 작은 원판만 놓을 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다. 다음 K줄에 A B 형태로 A번 장대에서 B번 장대로 옮기는 과정을 출력한다.

3

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3