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

Майже безпрефіксні коди

Майже безпрефіксні коди

У теорії кодування часто використовують безпрефіксні коди - набори слів, жодне з яких не є префіксом іншого. Наприклад, набір слів "\textbf{aba}", "\textbf{aa}" та "\textbf{bac}" є безпрефіксним кодом, а набір "\textbf{abac}", "\textbf{aba}", "\textbf{ba}" - ні, оскільки слово "\textbf{aba}" є префіксом слова "\textbf{abac}". Професор Дешифро працює у лабораторії досліджень нікому не потрібної інформації і вивчає свій новий винахід - майже безпрефіксні коди. Набір слів називається майже безпрефіксним кодом рівня \textbf{k}, якщо найбільший спільний префікс двох довільних слів з набору не перевищує по довжині \textbf{k}. Наприклад, набір "\textbf{abac}", "\textbf{abс}", "\textbf{ba}" є майже безпрефіксним кодом рівня \textbf{2}, а набір "\textbf{abac}", "\textbf{abab}", "\textbf{ba}" - ні, оскільки найбільший спільний префікс слів "\textbf{abac}" та "\textbf{abab}" має довжину \textbf{3}. Чергова задача, яку професор Дешифро поставив своїм лаборантам, полягає у наступному: за заданим набором слів та числом \textbf{k} потрібно вибрати із заданих слів максимальний набір, який є майже безпрефіксним кодом рівня \textbf{k}. Вам, як молодшому лаборанту, доручили написати відповідну програму. \InputFile Перший рядок вхідного файлу містить два цілих числа: \textbf{n} та \textbf{k} - кількість слів у заданому наборі та рівень майже безпрефіксного кода, який потрібно побудувати (\textbf{1} ≤ \textbf{n} ≤ \textbf{100000}, \textbf{0} ≤ \textbf{k} ≤ \textbf{200}). Наступні \textbf{n} рядків містять по одному слову. Слова складаються з рядкових букв латинського алфавіту. Довжина кожного слова від \textbf{1} до \textbf{200 }символів. Сумарна довжина усіх слів не перевищує \textbf{10^6}. Усі слова різні. \OutputFile У першому рядку вихідного файлу виведіть одне число \textbf{m} - максимальну кількість слів, яку можна вибрати із заданого набору, щоб вони утворювали майже безпрефіксний код рівня \textbf{k}. Наступні \textbf{m} рядків повинні містити вибрані слова.
Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
6 2
aba
bacaba
abacaba
baca
abac
caba
Вихідні дані #1
3
aba
bacaba
caba