eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

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

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

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

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

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

Пример

Входные данные #1
ab
arc
arco
bar
bran
carbon
carbons
cobra
crab
crayon
narc
Выходные данные #1
ab
bar
crab
cobra
carbon
carbons