题目描述
原题来自：Centrual Europe 2005
我们有
n
n 个字符串，每个字符串都是由 a 至 z 的小写英文字母组成的。如果字符串
A
A 的结尾两个字符刚好与字符串
B
B 的开头两个字符匹配，那么我们称
A
A 与
B
B 能够相连（注意：
A
A 能与
B
B 相连不代表
B
B 能与
A
A 相连）。我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。如下例：
ababc
bckjaca
caahoynaab
第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为
5+7+10=22
5+7+10=22（重复部分算两次），总共使用了
3
3 个串，所以平均长度是
\frac{22}{3}\approx 7.33
22/3
≈7.33。
输入
本题有多组数据。
每组数据的第一行，一个整数
n
n，表示字符串数量；
接下来
n
n 行，每行一个长度小于等于
1000
1000 的字符串。
读入以
0
0 结束。
输出
若不存在环串，输出 No solution，否则输出最长的环串的平均长度。
只要答案与标准答案的差不超过
0.01
0.01，就视为答案正确。
样例输入
3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0
样例输出
21.66
提示
数据范围与提示
对于全部数据，
1\le n\le 10^5
1≤n≤105。
来源/分类
ybttg 负环 二分