题目描述

给定三根柱子，记为 A、B 和 C 。起始状态下，柱子 A 上套着 $n$ 个圆盘，它们从上到下按照从小到大的顺序排列。我们的任务是要把这 $n$ 个圆盘移到柱子 C 上(如下图)，并保持它们的原有顺序不变。

在移动圆盘的过程中，需要遵守以下规则:

• 1.圆盘只能从一根柱子顶部拿出，从另一根柱子顶部放入。
• 2.每次只能移动一个圆盘。
• 3.小圆盘必须时刻位于大圆盘之上。

输入盘子数量 $n$ ，盘子编号从上往下依次为 $1\sim n$,请输出移动过程 ，最后输出移动方案数。

输入格式

一个整数，表示盘子数量。

输出格式

若干行，表示移动过程，每行格式如下格式：

id [A] -> [C]

表示编号为 id 的盘子从 [A] 柱子移动到 [C] 柱子。

接下来一行输出移动总次数。

2

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

样例解释

移动过程如下：

3

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

数据规模与约定

$1\leq n\leq 20$