#Pybt2420. 九连环

九连环

九连环

题目描述

九连环是我国的传统民间智力玩具,总共9个环互相连接。一些环在框柄上,一些不在,例如下图中第4和第9个环在框柄上,其他环不在。

![1.jpg](file://55b8bd8782.jpg)

我们称把某个环从框柄上取下为off操作,把环放到框柄上为on操作。

第1个环可以在任何时候取下或放上。对于大于1的整数n,必须恰好第n-1个环在框柄上,编号小于n-1的环都不在框柄上,才可以被取下或放上。

例如需要放上第5个环,那么得先保证第1,2,3个环不在框柄上,第4个环在框柄上,此时可以把第5个环放上框柄。

现在有一个连环,所有环都在框柄上。需要取下所有的环,输出步数最少的操作过程。

实际中第1个环和第2个环是可以一起取下或放上的,但为了处理方便,我们不允许它们同时操作。

输入格式

从标准输入读入数据。

一行一个正整数n,表示环的数量。保证n<=18。

输出格式

输出到标准输出。

输出若干行表示方案。每行为一个操作,格式为环的编号、操作名称,之间用一个空格隔开。

数据范围

(原站未提供,导入后需人工补齐)

样例

3
1 off
3 off
1 on
2 off
1 off
4
2 off
1 off
4 off
1 on
2 on
1 off
3 off
1 on
2 off
1 off
5
1 off
3 off
1 on
2 off
1 off
5 off
1 on
2 on
1 off
3 on
1 on
2 off
1 off
4 off
1 on
2 on
1 off
3 off
1 on
2 off
1 off