TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2224
  • Problem
  • P2224【欧拉】接龙句子
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    有多个单词,如果一个单词的结尾字母跟另一个单词的开始字母相同,那么它们就构成了接龙对,就用点号"."连接,如下列例子所示:
    dog.gopher
    gopher.rat
    rat.tiger
    aloha.aloha
    arachnid.dog
    一个接龙句是指三个以上的由点号相连的接龙对构成的句子,例如,上面的例子中的接龙对可构成下列接龙句:
    aloha.aloha.arachnid.dog.gopher.rat.tiger

    给出若干单词,请找出包含所有单词的接龙句,每个单词在句子中只能出现一次

    Input Format

    第一行,一个整数t(t<=20)表示有t组测试数据,对于每组册数数据:

    第一行,一个整数n( 3 <= n <= 1000 ),表示单词的个数。
    接下来n行,每行一个长度不超过20的由小写字母构成的单词。

    Output Format

    对于每组测试数据:
    输出字典序最小的一个接龙句。
    如果无解,输出"***"

    Sample Input

    2
    6
    aloha
    arachnid
    dog
    gopher
    rat
    tiger
    3
    oak
    maple
    elm

    Sample Output

    aloha.arachnid.dog.gopher.rat.tiger
    ***


    Source  欧拉 Waterloo local 2003.01.25 poj2337