#P18065. Word Generator
Word Generator
Word Generator
一台机器有 个槽位,从左到右编号为 。第 个槽位只能使用为它准备的字母卡片。每个槽位各放入一张卡片后,依次连接卡片上的字母,就得到一个长度为 的单词。
每张卡片最多使用一次。同一个槽位中即使有多张相同字母的卡片,它们也是不同的卡片。
如果一个单词中的所有字母两两不同,就称它为美丽单词。你需要生成尽可能多的美丽单词,并输出一种方案。不同次生成的单词允许相同;限制是卡片不能重复使用,以及每个单词内部的字母不能重复。
输入格式
第一行一个整数 ,表示测试用例数。
每组数据第一行一个整数 。接下来 行,第 行为一个非空字符串 ,其中每个小写英文字母表示第 个槽位可用的一张卡片。
输出格式
对每组数据,先输出一个整数 ,表示最多可以生成的美丽单词数;再输出 行,每行一个长度为 的美丽单词。
有多种最优方案时,可以输出任意一种。
数据范围
,,所有字符串只含小写英文字母。所有测试用例中所有 的总和不超过 。
样例
2
4
aaab
abcd
ccd
ade
3
aaabc
abbbc
abccc
3
bcda
adce
abcd
5
abc
abc
abc
cab
bca