h267. 汉诺塔搬运记录

题目描述

有三根柱子 A、B、C。开始时，$n$ 个大小不同的圆盘按从大到小的顺序叠在 A 柱上。每次只能移动一个圆盘，且大圆盘不能放在小圆盘上。

请用最少步数把所有圆盘从 A 柱移动到 C 柱，并输出完整移动记录。

输入格式

输入一个整数 $n$。

输出格式

第一行输出最少移动步数。

接下来每行输出两个柱子名称，表示把一个圆盘从第一个柱子移动到第二个柱子。

数据范围

• $1\le n\le 12$
• 最少移动步数不超过 $4095$。

样例

输入

2

输出

3
A B
A C
B C

标签：递归、汉诺塔