三角形图

题目背景

模拟赛一道难过到我的题

题目描述

一个三角形网格上,每个小三角形的面积都为1。你可以从某个点开始,沿着边走出一个多边形来,使得围成一定的面积。我们可以给每个点定义5个方向: a 左转120° b 左转60° c 直走 d 右转60° e 右转120° 这样的话,一个图形就能被一组字母表示出来。 ![](https://cdn.luogu.org/upload/pic/1430.png) ![](https://cdn.luogu.org/upload/pic/1423.png) 比如左边的图,从A点开始顺时针走,则可以表示为dcddeaddd;从B点开始顺时针走,则可以表示ddeaddddc;……。右图显示的是左图翻折后的情况。 左图和右图是本质相同的图形。为了惟一地表示一类全等的图形,我们在这类图形的所有表示方法中找字典序最小的表示方法来代表这一类全等的图形。左图和右图的最小表示方法相同,都是addddcdde。 现在告诉你一个图形的某个表示法(不一定是最小表示方法),请你求出在这个图形的基础上加一个小三角形后合法图形的个数,以及他们的最小表示方法。 一个图形是合法的,当且仅当组成它的所有小三角形均有至少一条与其他三角形公共的边,且不存在中空。 下面的图形都是不合法的: ![](https://cdn.luogu.org/upload/pic/1425.png) ![](https://cdn.luogu.org/upload/pic/1426.png) ![](https://cdn.luogu.org/upload/pic/1427.png) ![](https://cdn.luogu.org/upload/pic/1428.png)

输入输出格式

输入格式


第一行1个数字T,表示数据组数。 接下来T行每行一个字符串,表示某个图形的某个表示方法。 读入数据保证一定合法,且一定是顺时针的表示方法。

输出格式


对于每组数据: 第一行1个整数K,表示加一个小三角形后的不全等的图形的个数。 接下来一行K个字符串,表示这K个不同图形的最小表示方法(按字典序排序),字符串两两之间用一个空格隔开,最小表示方法必须是顺时针的。 两组数据间用一个空行隔开。

输入输出样例

输入样例 #1

Sample Input 1:
2
eee
cedde
Sample Input 2:
2
adeccecced
dddddd

输出样例 #1

Sample Output 1:
1
dede

3
beddde cdecde cecece
Sample Output 2:
5
acedccecced addebcecced adebebecced adecbedcced cceccecce

1
cddddce

说明

样例解释 Sample 1 的解释: ![](https://cdn.luogu.org/upload/pic/1429.png)