|
Всем известны правила игры в города: первый игрок называет произвольный
город, следующий - город, название которого начинается на ту же букву, на
которую заканчивается название предыдущего города, и т.д. Аналогичным образом
можно играть не в названия городов, а, например, в названия животных. Задан
список допустимых для описанной игры слов, слова в нем могут повторяться.
Напишите программу, определяющую, в каком порядке в процессе игры должны быть
названы слова из списка, чтобы каждое слово было использовано ровно столько
раз, сколько оно в нем встречается.
Input
В первой строке входного файла записано целое число N - количество слов в
списке (1 ≤ N ≤ 1000), а в последующих N строках - сами слова.
Каждое из них является последовательностью не более чем из 10 строчных
английских букв.
Output
Выведите в выходной файл слова в искомом порядке, либо сообщение NO, если
такого порядка не существует. Каждое слово должно быть выведено в отдельную
строку выходного файла.
Sample
| Input | Output |
|---|
4
b
ab
bc
bb | ab
bb
b
bc |
Solution
Составим ориентированный мультиграф (мультиграфом называется граф, в котором пары вершин могут быть
соединены более чем одним ребром), вершинами которого будут являться
буквы от a до z. Каждому слову из списка сопоставим ребро, соединяющее
первую и последнюю буквы этого слова. В полученном мультиграфе требуется
найти эйлеров путь (т.е. путь, проходящий по каждому ребру ровно один раз).
Алгоритм построения такого пути можно найти, например, в [Липский 88,п. 2.7].
|
