Майже безпрефіксні коди#4675
У теорії кодування коди без префіксів — це множини слів, у яких жодне слово не є префіксом іншого. Наприклад, множина слів aba, aa та bac є кодом без префіксів, в той час як множина abac, aba, ba — ні, оскільки aba є префіксом abac.
Професор Дешифро, який працює у лабораторії дослідження зайвої інформації, досліджує свій останній винахід — майже коди без префіксів. Множина слів називається майже кодом без префіксів рівня , якщо для будь-яких двох слів цієї множини їхній найдовший спільний префікс має довжину не більше символів. Наприклад, множина abac, abc, ba є майже кодом без префіксів рівня , а множина abac, abab, ba — ні, оскільки найдовший спільний префікс abac та abab має довжину .
Останнє завдання, яке професор Дешифро дав своїм асистентам, таке: маючи множину слів і число , знайти найбільшу підмножину з цих слів, яка є майже кодом без префіксів рівня . Як молодший асистент лабораторії, ви повинні написати програму для розв'язання цієї задачі.
У першому рядку містяться два цілих числа та (1 \leq n \leq 100\,000, 0 \leq k \leq 200) — кількість слів у множині та рівень майже коду без префіксів, який потрібно побудувати. Далі в кожному з наступних рядків записано слово, що складається з малих латинських літер. Довжина кожного слова від до . Сумарна довжина всіх слів не перевищує 10^6. Усі слова різні.
Виведіть максимальне число слів, які можна вибрати з даної множини, щоб утворити майже код без префіксів рівня . Далі виведіть вибрані слова — по одному в рядку.
Приклад 1