Смешивание и построение

В этой задаче Вам задана последовательность слов (последовательность строчных букв). В этой последовательности необходимо найти наибольшую подпоследовательность слов w₁, ..., w_n такую, что w_i есть смешанным расширением w_i-1. Слово A есть смешанным расширением слова B если A можно получить из букв слова B и добавлением только одной новой буквы а также последующей их перестановкой. Например, "ab", "bar", "crab", "cobra", и "carbon" есть такая последовательность длины 5.

Технические условия

Входные данные

Каждый тестовый блок содержит как минимум две но не более 10000 строк. В каждой строке только одно слово. Длина слова не менее 1 и не более 20. Все слова в блоке различны.

Выходные данные

Вывести наиболее длинную цепочку слов, которая может быть построена из заданных слов. Слова выводить начиная с первого. Если существует несколько таких максимальных цепочек, выведите любую.

Информация о задаче

Лимит времени: 2 секунды
Лимит памяти: 64 MB
Баллы за пройденный тест: 11.1111
Сложность: 20% 8/10
Классификация: Алгоритмы на строках

Пример

Пример входных данных

ab
arc
arco
bar
bran
carbon
carbons
cobra
crab
crayon
narc

Пример выходных данных

ab
bar
crab
cobra
carbon
carbons

← GATTACA

Список задач