P1386. 单词游戏

问题描述

一些秘密的门包含一个非常有趣的单词拼图。考古学家团队必须解决它才能打开这些门。因为没有其他方法可以打开门，所以这个拼图对我们来说非常重要。

每个门上都有许多磁性板。每块板上写有一个单词。这些板必须按照以下规则排列成一个序列：每个单词的首字母必须与前一个单词的尾字母相同。例如，单词“acm”后面可以跟单词“motorola”。你的任务是编写一个计算机程序，读取单词列表，并确定是否可以按照给定规则排列所有板，从而打开门。

输入

输入包含 $T$ 个测试用例。输入文件的第一行给出测试用例的数量 $T$。每个测试用例以一行开始，包含一个整数 $$N（1 ≤ N ≤ 100000）$$，表示板的数量。接下来是 $N$ 行，每行包含一个单词。每个单词包含至少两个且最多 $1000$ 个小写字母，即只有 $'a'$ 到 $'z'$ 的字母会出现。列表中可能会出现相同的单词多次。

输出

你的程序需要确定是否可以将所有板排列成一个序列，使得每个单词的首字母等于前一个单词的尾字母。列表中的所有板都必须使用，每个恰好一次。如果单词在列表中出现多次，则必须使用相应次数。

如果存在这样的排列顺序，你的程序应输出句子 "Ordering is possible."。否则，输出句子 "The door cannot be opened."。

输入示例 1

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

输出示例 1

The door cannot be opened.
Ordering is possible.
The door cannot be opened.

来源

Central Europe 1999

如果需要进一步帮助，请告诉我！