EOJ-自适应编程学习平台

“传说大梵天在创造世界时做了三根金刚石柱子，在一根柱子上从下往上从大到小摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘......”

一觉醒来，$Kilo$ 竞穿越到了古印度。

$Kilo$ 面前同样是三根柱子。但和课上听到的传说不一样的是，这些柱子不是金刚石做的，圆盘也不是黄金做的。这时，一个声音从天边传来：“要想回到原来的世界，你就得把圆盘从下面开始...”

“我知道，”$Kilo$ 打断了那个声音，“从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。”

看着面前 $A, B, C$ 三根柱子，$Kilo$ 陷入了沉思。现在，$n$ 个圆盘从下往上，从小到大摞在 $A$ 上。

$Kilo$ 想要尽可能早地回家，你能否给 $Kilo$ 一个方案，以最少的移动次数将 $n$ 个圆盘从 $A$ 挪到 $B$ ？

一行一个整数 $n$ ($1 \le n \le 20$) 。

第一行一个整数 $k$，代表最少需要的移动次数。

接下来 $k$ 行中，第 $i$ 行两个大写字母 $X_i, Y_i$，代表第 $i$ 步将 $X_i$ 柱顶端的圆盘移到 $Y_i$ 柱上。