题目描述

我们有$n$个字符串，每个字符串都是由a~z的小写英文字母组成的。如果字符串 A的结尾两个字符刚好与字符串 B 的开头两个字符相匹配，那么我们称A与B能够相连(注意:A能与B相连不代表B能与A相连)。

我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串(一个串首尾相连也算)，我们想要使这个环串的平均长度最大。

如下例:

ababc
bckjaca
caahoynaab

第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为5+7+10 =22(重复部分算两次)，总共使用了3个串，所以平均长度是22/3≈7.33.

输入格式

本题有多组数据

每组数据的第一行，一个整数$n$，表示字符串数量

接下来$n$行，每行一个长度小于等于1000的字符串

读入以$n=0$结束

输出格式

若不存在环串，输出”No solution”，否则输出最长的环串的平均长度,结果保留两位小数

3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0​

21.66​

提示

$1≤n≤10^5$