Задачі
Смешивание и построение
Смешивание и построение
У цій задачі Вам задано послідовність слів (послідовність рядкових літер). У цій послідовності необхідно знайти найбільшу підпослідовність слів \textbf{w_1}, ..., \textbf{w_n} таку, що \textbf{w_i} є \textit{змішаним розширенням} \textbf{w_\{i-1\}}. Слово \textbf{A} є змішаним розширенням слова \textbf{B} якщо \textbf{A} можна отримати з літер слова \textbf{B} і додаванням лише однієй нової літер а також наступної їх перестановки. Наприклад, "\textbf{ab}", "\textbf{bar}", "\textbf{crab}", "\textbf{cobra}", і "\textbf{carbon}" є така послідовність довжини \textbf{5}.
\InputFile
Кожен тестовий приклад містить як мінімум два але не більше \textbf{10000} рядків. У кожному рядку є лише одне слово. Давжина слова не менше \textbf{1} і не більше \textbf{20}. Всі слова у блоці відмінні.
\OutputFile
Вивести найбільш довгий ланцюжок слів, який можна побудувати із заданих слів. Слова виводити починаючи з першого. Якщо існує декілька таких максимальних ланцюжків, виведіть довільний.
Вхідні дані #1
ab arc arco bar bran carbon carbons cobra crab crayon narc
Вихідні дані #1
ab bar crab cobra carbon carbons