TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2224
  • 题目
  • P2224【欧拉】接龙句子
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

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

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

    输入格式

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

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

    输出格式

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

    样例输入

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

    样例输出

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


    来源  欧拉 Waterloo local 2003.01.25 poj2337