比赛场次	118
比赛名称	20120217
比赛状态	已结束比赛成绩
开始时间	2012-02-17 19:00:00
结束时间	2012-02-17 22:00:00
开放分组	全部用户
组织者	cqw
注释介绍

题目名称	分球
输入输出	`balls.in/out`
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试点数	8 简单对比

用户	结果	时间	内存	得分
Citron酱	WWWWWWEE	0.000 s	0.00 MiB	0
Launcher	WWWWWWWW	0.000 s	0.00 MiB	0
苏轼	WWWWWWWW	0.000 s	0.00 MiB	0
Makazeu	RRRRRRRR	0.000 s	0.00 MiB	0
Truth.Cirno	WWWWTTTT	0.000 s	0.00 MiB	0
皪林展也	WWWWWWWW	0.000 s	0.00 MiB	0
Yeehok	WWWWWWWW	0.000 s	0.00 MiB	0
王者自由	C	0.000 s	0.00 MiB	0

2. 分球

★☆ 输入文件：balls.in 输出文件：balls.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

在一个装满财宝的屋子里，有2N个盒子排成一排。除了两个相邻的空盒外，其余的每个盒子里都装有一个金球或者一个银球，总共有N-1个金球和N-1个银球。用图6．3所示为一个N=5时的例子，G表示金球，S表示银球。

任意两个相邻的非空的盒子里的球可以移动到两个相邻的空盒中，移动不能改变这两个球的排列顺序。写一个程序，用最少的移动次数把所有的金球都移到所有的银球的左边。

【输入格式】

输入文件包含多组数据。第一行为K，表示数据的总数。

每组数据的第一行是N(3≤N≤7)，

第二行是2N个盒子的初始状态。金球用a表示，银球用b表示，空盒用空格表示。每两组相邻数据用空行隔开。

【输出格式】

对于每一组数据，若无解则输出一行NO SOLUTION，若有解，输出一组状态来表示移动的序列，每个状态占一行。每行输出到此状态的移动的步数，紧接着是一个空格，然后是此时的状态。初始状态为第0步，每组数据都要先输出初始状态。如有多种最少移动次数的方案，输出“空格靠前靠左”的一种，如下两种方案，需输出第二种。

0 bbbb  aaaa
         1 bbbbaa   aa
         2    bbaabbaa
         3 aabbaabb
         4 aa  aabbbb

0 bbbb aaaa
         1    bbbbaaaa
         2 aabbbb  aa
         3 aa  bbbbaa
         4 aaaabbbb

相邻的两组数据用一个空行隔开。

【输入输出样例】

样例输入（balls.in）:

3
3
abab  

5
abba  abab

6
a  babbababa

样例输出（balls.out）：

NO SOLUTION

0 abba  abab
1 abbabaa  b
2 a  abaabbb
3 aaaab  bbb

0 a  babbababa
1 aabbabb  aba
2 aabbabbbaa
3 aa  abbbaabb
4 aaaaabbb  bb