31248번 - 3+1 하노이 탑 스페셜 저지

3+1 하노이 탑 게임은 가로 방향으로 일렬로 놓인 4개의 기둥과 크기가 서로 다른 $N$개의 원판을 이용한 게임이다. 편의상 왼쪽에 있는 기둥부터 차례대로 A, B, C, D라고 하자.

처음에는 기둥 A에 크기가 가장 큰 원판이 아래에 오도록 모든 원판이 크기 순서대로 쌓여 있다. 이 게임의 목표는 아래 규칙을 지키면서 모든 원판을 기둥 D로 옮기는 것이다.

• 한 번에 1개의 원판만 옮길 수 있다.
• 어떤 기둥의 맨 위에 있는 원판만 옮길 수 있다.
• 작은 원판 위에 큰 원판을 놓을 수 없다.
• 기둥 D에 있는 원판을 다른 기둥으로 옮길 수 없다.
• 기둥 A, B, C에 있는 원판은 위 조건을 어기지 않는 한 자유롭게 옮길 수 있다.

기둥 A에 있는 $N$개의 원판을 모두 기둥 D으로 옮기기 위해 필요한 최소 이동 횟수를 구하고, 그러한 이동 방법을 아무거나 하나 출력하시오.

첫 번째 줄에 정수 $N$이 주어진다.

첫 번째 줄에 원판을 모두 옮기기 위해 필요한 최소 이동 횟수 $M$을 출력한다.

다음 줄부터 $M$줄에 걸쳐서 한 줄에 원판의 이동을 하나씩 출력한다. 원판을 기둥 X에서 기둥 Y로 옮겼을 때 X Y의 형태로 출력한다.

• $1\le N\le 20$