#P18065. Word Generator

Word Generator

Word Generator

一台机器有 MM 个槽位,从左到右编号为 1,2,…,M1,2,\ldots,M。第 ii 个槽位只能使用为它准备的字母卡片。每个槽位各放入一张卡片后,依次连接卡片上的字母,就得到一个长度为 MM 的单词。

每张卡片最多使用一次。同一个槽位中即使有多张相同字母的卡片,它们也是不同的卡片。

如果一个单词中的所有字母两两不同,就称它为美丽单词。你需要生成尽可能多的美丽单词,并输出一种方案。不同次生成的单词允许相同;限制是卡片不能重复使用,以及每个单词内部的字母不能重复。

输入格式

第一行一个整数 TT,表示测试用例数。

每组数据第一行一个整数 MM。接下来 MM 行,第 ii 行为一个非空字符串 SiS_i,其中每个小写英文字母表示第 ii 个槽位可用的一张卡片。

输出格式

对每组数据,先输出一个整数 CC,表示最多可以生成的美丽单词数;再输出 CC 行,每行一个长度为 MM 的美丽单词。

有多种最优方案时,可以输出任意一种。

数据范围

1≤T≤1031\le T\le 10^3,1≤M≤261\le M\le26,所有字符串只含小写英文字母。所有测试用例中所有 ∣Si∣|S_i| 的总和不超过 10610^6。

样例

2
4
aaab
abcd
ccd
ade
3
aaabc
abbbc
abccc
3
bcda
adce
abcd
5
abc
abc
abc
cab
bca