题目描述

原题来自：Centrual Europe 205

我们有 $\red{n }$个字符串，每个字符串都是由 a 至 z 的小写英文字母组成的。如果字符串 $\red{A}$ 的结尾两个字符刚好与字符串 $\red{B}$ 的开头两个字符匹配，那么我们称 $\red{A}$ 与 $\red{B}$ 能够相连（注意：$\red{A}$ 能与 $\red{B}$ 相连不代表 $\red{B}$ 能与 $\red{A }$相连）。我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。如下例：

$\red{ababc}$ $\red{bckjaca}$ $\red{cAhoynAb}$

第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串能与第一个串相连，我们按照此顺序相连，便形成了一个环串，长度为 $\red{5+7+10=22}$（重复部分算两次），总共使用了 $\red{3 }$个串，所以平均长度是$\red{ \frac{22}{3}\approx 7.33}$。

输入格式

本题有多组数据。

每组数据的第一行，一个整数$\red{ n}$，表示字符串数量； 接下来$\red{ n }$行，每行一个长度小于等于 $\red{100 }$的字符串。

读入以 $\red{0}$ 结束。

输出格式

若不存在环串，输出 No solution，否则输出最长的环串的平均长度。

只要答案与标准答案的差不超过$\red{ 0.01}$，就视为答案正确。

样例

输入样例

3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0

输出样例

21.66

提示

对于全部数据，$\red{1≤n≤10^5}$。