我们有n个(n<=100000)字符串,每个字符串都是由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”。否则输出最长的环串平均长度。