#777. Vòng tròn từ ngữ (WORDRINGS)

Chúng ta có chuỗi ký tự, mỗi chuỗi bao gồm các chữ cái tiếng Anh in thường từ a đến z. Nếu hai ký tự cuối cùng của chuỗi trùng khớp hoàn toàn với hai ký tự đầu tiên của chuỗi , ta nói rằng có thể nối với (Lưu ý: nối được với không có nghĩa là nối được với ). Chúng ta muốn chọn ra một số chuỗi từ các chuỗi đã cho để nối chúng lại thành một vòng tròn (một chuỗi tự nối đầu đuôi với chính nó cũng được tính), và muốn độ dài trung bình của vòng tròn này là lớn nhất. Ví dụ:

Chuỗi thứ nhất nối được với chuỗi thứ hai, chuỗi thứ hai nối được với chuỗi thứ ba, chuỗi thứ ba nối được với chuỗi thứ nhất. Theo thứ tự này, chúng tạo thành một vòng tròn có tổng độ dài là (phần trùng lặp được tính hai lần), tổng cộng sử dụng chuỗi, vậy độ dài trung bình là .

Dữ liệu:

• Bài này có nhiều bộ dữ liệu (multitest).
• Dòng đầu tiên của mỗi bộ dữ liệu là một số nguyên , biểu thị số lượng chuỗi.
• Tiếp theo là dòng, mỗi dòng chứa một chuỗi có độ dài nhỏ hơn hoặc bằng .
• Dữ liệu kết thúc khi gặp số .

Kết quả:

• Nếu không tồn tại vòng tròn nào, xuất No solution, ngược lại xuất độ dài trung bình của vòng tròn dài nhất.
• Đáp án được coi là đúng nếu sai lệch không quá so với đáp án chuẩn.

Ví dụ:

Dữ liệu:

3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
0

Kết quả:

21.66

Giới hạn: .