单词接龙

题目背景

【提示】本题使用`string`类实现较为方便。 `string`类的`s.substr(pos,k)`方法的返回值为 s 串从`s[pos]`开始的长度为`k`的子串,例如: ``` string s = "bbbhjj"; string t = s.substr(2,3); ``` 则 字符串 `t = bhj`。

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词(所有单词互不相同且长度相等),将所有单词连成一条“龙”(每个单词出现恰好1次)。在两个单词相连时,其重合部分合为一部分,例如 beast 和 astonish,如果接成一条龙则变为 beastonish;若没有重合部分,则直接首尾相连,例如 code 和 forces 相连变为 codeforces。 在保证每个单词出现恰好1次的前提下,请你求出“龙”的最短长度。 例如有4个单词: aa ab ba bb 最短的龙为:aa-ab-bb-ba 相连为 aabba,长度为5。

输入输出格式

输入格式


第一行1个正整数 n,代表单词数量 接下来 n 行,每行1个字符串代表一个单词,保证所有单词互不相同且长度相等、仅包含小写字母。

输出格式


第一行输出1个整数,代表“龙”的最小长度。 第二行输出1个字符串,代表最短的“龙”(若有多个,输出字典序最小的)。

输入输出样例

输入样例 #1

4
aa
ab
bb
ba

输出样例 #1

5
aabba

输入样例 #2

5 
aaaab 
bbaab 
bbbaa 
bbaaa 
abbaa

输出样例 #2

12 
bbbaaaabbaab

输入样例 #3

10 
babaaabbaa 
aaabbaabba 
bbbbbaaaab 
aabaaaabab 
bbbaaaabaa 
abaaaaabab 
aaaabaaaaa 
abbbababbb 
abbaaabbba 
bbbaababba

输出样例 #3

55
aabaaaababaaabbaabbaaabbbababbbbbaaaabaaaaababbbaababba

说明

设 $s$ 为单词最大长度 对于20%的数据,$1 \le n,s \le 5$ 对于40%的数据,$1 \le n,s \le 8$ 对于60%的数据,$1 \le n,s \le 10$ 对于80%的数据,$1 \le n \le 15,1 \le s \le 10$ 对于100%的数据,$1 \le n \le 15,1 \le s \le 15$