#240. 芝麻开门

芝麻开门

题目描述

在未来的城市中,有一座高度智能化的大楼,控制着整个城市的能源和网络流量。大楼的最深处,有一扇古老的电子门,它是城市网络的核心入口,只有成功解锁这扇门,才可以控制整个城市的系统。

然而,这扇门并不容易打开。它的安全系统非常复杂,要求输入一组关键词,这些关键词必须按照特定的规则排列。规则是这样的:每个关键词的最后一个字母必须和下一个关键词的第一个字母相同。通过这种方式,所有的关键词需要串联成一个连续的“链条”,就像一个闭合的环。

举个例子,假设有以下几个词:

  • "acm" 的结尾是 "m",而 "motor" 的开头是 "m",所以可以连接这两个词;
  • "motor" 的结尾是 "r",而 "radar" 的开头是 "r",因此它们也可以连接。

如果能通过这种连接规则把所有关键词连接成一个完整的链条,电子门就会自动解锁,允许你控制整个城市的网络。如果不能,则门将无法开启。

现在,作为城市最顶尖的程序员,你的任务是检查这些给定的关键词,看看是否能够按照规则排列它们,开启大门。你能成功吗?

输入描述

输入的第一行包含一个整数 TT,表示测试用例的数量。每个测试用例由以下内容组成:

  • 第一行包含一个整数 NN,表示关键词的数量 (1N1000001 \leq N \leq 100000)。
  • 接下来的 NN 行,每行包含一个由小写字母组成的单词。每个单词的长度在 2 到 1000 个字符之间。

输出描述

对于每个测试用例,输出一个结果:

  • 如果可以找到一种排列顺序,使得所有关键词按照要求拼接在一起,输出 Ordering is possible.

  • 否则输出 The door cannot be opened.

    样例

    3
    5
    apple
    elephant
    tank
    key
    yarn
    3
    grape
    elephant
    tiger
    4
    cat
    tag
    dog
    goose
    
Ordering is possible.
Ordering is possible.
The door cannot be opened.