Catenym là một cặp từ cách nhau bằng một dấu chấm ('.') sao cho mã ký tự cuối cùng của từ đầu tiên giống như ký tự đầu tiên của từ thứ 2. Ví dụ sau đây là các catenym
dog.gopher
gopher.rat
rat.tiger
aloha.aloha
arachnid.dog
Một dãy catenym là một dãy gồm 3 hoặc nhiều từ cách nhau bằng dấu ('.') mà mỗi cặp từ liền kề tạo thành một catenym. Ví dụ: aloha.aloha.arachnid.dog.gopher.rat.tiger
Yêu cầu: Cho trước một từ điển chứa các từ, hãy tìm một dãy catenym chứa mỗi từ trong từ điển đúng một lần
Dữ liệu: Vào từ file văn bản catenym.inp gồm:
. dòng đầu chứa số nguyên dương n(1<=n<=1000) số từ trong từ điển
. các dòng tiếp theo chứa các từ phân biệt trong từ điển, mỗi từ chứa không quá 20 ký tự chữ in thường 'a'..'z'
kết quả: ghi ra file văn bản catenym.out chứa dãy catenym chứa mỗi từ trong từ điển đúng một lần. Nếu không có lời giải ghi ra '***'
Ví dụ1
8
ab
bc
cd
da
ce
ef
fg
ge
file cần là: cd.da.ab.bc.ce.ef.fg.ge
ví dụ 2
10
oak
maple
elm
file cần là: ***