{"trustable":true,"sections":[{"title":"题目描述","value":{"format":"MD","content":"**Original problem from: Centrual Europe 2005**\n\nWe have $n$ strings, each consisting of lowercase English letters from \u0027a\u0027 to \u0027z\u0027. If the last two characters of string $A$ exactly match the first two characters of string $B$, then we say that $A$ can be connected to $B$ (note that $A$ being able to connect to $B$ does not imply that $B$ can connect to $A$). We want to find some strings from the given set that can be connected end to end to form a circular string (a string connected end to end also counts), and we want to maximize the average length of this circular string. For example:\n\n\u003eababc \nbckjaca \ncaahoynaab\n\nThe first string can be connected to the second string, the second string can be connected to the third string, and the third string can be connected to the first string. By connecting them in this order, we form a circular string with a length of $5+7+10\u003d22$ (repeated parts count twice), using a total of $3$ strings, so the average length is $\\frac{22}{3}\\approx 7.33$."}},{"title":"Input Format","value":{"format":"MD","content":"There are multiple test cases for this problem.\n\nFor each test case:\nThe first line contains an integer $n$, indicating the number of strings.\nThe next $n$ lines each contain a string of length at most $1000$.\n\nInput ends with $0$."}},{"title":"Output Format","value":{"format":"MD","content":"If no circular string exists, output `No solution`. Otherwise, output the average length of the longest circular string.\n\nAn answer is considered correct if its difference from the standard answer is not more than $0.01$."}},{"title":"Sample","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\nintercommunicational\nalkylbenzenesulfonate\ntetraiodophenolphthalein\n0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e21.66\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Data Range and Hints","value":{"format":"MD","content":"For all data, $1\\le n\\le 10^5$."}}]}