UOJ Logo Universal Online Judge

UOJ

#152. 【UR #10】汉诺塔

统计

picks 博士乘上时光机器,打算回到 2012 年化身马猴烧酒阻止金星凌日,挽救世风日下的 OI 界于水火之中。

但是不幸的是,时光机器出现了一些特殊的故障,picks 博士被传送到了一个未知的时空。为了修理时光机器,他必须要得到一种叫做巴拉拉能量的能源。经过调查,他发现在这个时空中存在着一个被当地人称为魔仙堡的领域,从生活在那儿的小魔仙那里就可以得到足够的巴拉拉能量。

然而在那个时空中,存在着一股强大的势力与善良的小魔仙们敌对——那就是邪恶的黑魔仙们。巴拉拉能量是不能被黑魔仙得到的,否则就会产生严重的后果。为了检验 picks 博士是否是黑魔仙派来窃取巴拉拉能量的奸细,睿智的魔仙女王给 picks 博士出了一道题:

我现在使用巴拉拉能量造了三根柱子(编号分别为 $1$ 到 $3$)以及 $n$ 块颜色不同的圆盘(编号为 $1$ 到 $n$)。最开始我给定一个 $1$ 到 $n$ 的排列 $A$,我会用巴拉拉能量把这些圆盘放到编号为 $1$ 的柱子上,使得从上到下第 $i$ 块圆盘的编号是 $A_i$。

接着你可以进行若干次操作,每一次操作用两个整数 $a,b$ ($1 \leq a,b \leq 3,a \neq b$) 来描述,表示这次操作你将会把地 $a$ 根柱子最上面的圆盘取出,并放到第 $b$ 根柱子上去(如果当前第 $a$ 根柱子上不存在圆盘,这次操作将会被小魔仙们忽略)。最终你要使得这 $n$ 块圆盘在同一根柱子上,且从上到下编号依次递增(最终状态下所有圆盘可以在任意一根柱子上)。

小魔仙们虽然善良,但是他们的耐心并不是无限的,所以你必须在 $10^6$ 次操作内完成任务。

输入格式

第一行一个正整数 $n$。

第二行是一个 $1$ 到 $n$ 的排列 $A$,相邻数字之间恰有一个空格隔开。

输出格式

第一行输出一个整数 $K$($0 \leq K \leq 10^6$)。

接下来 $K$ 行每行两个整数 $a_i,b_i$,按照顺序依次描述你的每一次操作。

如果有多种方案,输出任意一种即可。

样例一

input

3
2 1 3

output

4
1 3
1 2
3 1
2 1

explanation

最开始三根柱子上的圆盘状态分别为$(2,1,3),(),()$。

第一次操作后圆盘状态为$(1,3),(),(2)$

第二次操作后圆盘状态为$(3),(1),(2)$

第三次操作后圆盘状态为$(2,3),(1),()$

第四次操作后圆盘状态为$(1,2,3),(),()$

在所有操作结束后,圆盘都在第一根柱子上且从上到下编号依次递增。

样例二

见样例数据下载。

限制与约定

测试点编号$n$ 的规模
1$n \leq 10$
2
3
4$n \leq 500$
5
6
7$n \leq 10000$
8
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载