하노이 탑

문제

기둥 A에 크기가 다른 원판 $n$개가 아래부터 큰 순서로 쌓여 있다. 원판은 1번이 가장 작고 $n$번이 가장 크다. 다음 규칙을 지키며 원판을 모두 기둥 C로 옮긴다.

• 한 번에 원판 하나만 옮긴다.
• 기둥 맨 위의 원판만 옮길 수 있다.
• 작은 원판 위에 큰 원판을 놓을 수 없다.

원판 $n$개를 옮기는 방법은 세 단계이다. 위의 $n-1$개를 A에서 B로 옮기고, 원판 $n$을 A에서 C로 옮긴 뒤, B의 $n-1$개를 C로 옮긴다.

이동 횟수가 가장 적은 방법으로 옮길 때 이동 횟수와 이동 과정을 출력한다.

제한

$1 \le n \le 15$

반복문 대신 재귀 함수로 푼다.

입출력 예시

입력 1

2

출력 1

3
1: A -> B
2: A -> C
1: B -> C

입력 2

3

출력 2

7
1: A -> C
2: A -> B
1: C -> B
3: A -> C
1: B -> A
2: B -> C
1: A -> C