汉诺塔步骤

难度：T2

【知识点：递归】【知识点：基本情况与返回顺序】

前置知识：函数、条件判断、整数拆位或按规则输出。

题目描述

三根柱子名为A、B、C。初始A上有 $n$ 个大小不同的圆盘，从顶部到底部由小到大。每次只能将某柱顶部的一个盘移到另一柱顶部，不能把大盘放在小盘上。借助B，将所有盘从A移到C，输出最少移动步骤。

输入格式

一行整数n。

输出格式

每次移动独占一行，先输出起点柱名，再一个空格，再终点柱名。不输出箭头、盘号或步数。

样例输入

2

样例输出

A B
A C
B C

样例说明

先将小盘从A移到B，再将大盘从A移到C，最后把小盘从B移到C。

数据范围

$1\le n\le12$。