Задача B. Почти беспрефиксные коды

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

В теории кодирования часто используют беспрефиксные коды – наборы слов, ни одно из которых не является префиксом другого. Слово α называется префиксом слова β, если α получается из β удалением нуля или более символов в конце. Например, слова «», «a», «ab» и «aba» являются префиксами слова «aba». Например, набор слов «aba», «aa» и «bac» является беспрефиксным кодом, а набор «abac», «aba», «ba» – нет, поскольку слово «aba» является префиксом слова «abac».

Профессор главного университета города Соколовка де Фрошин дает задания нерадивым студентам по кодированию информации – почти беспрефиксные коды. Набор слов называется почти беспрефиксным кодом уровня k, если наибольший общий префикс двух любых слов из набора не превышает по длине k. Например, набор «abac», «abс», «ba» является почти беспрефиксным кодом уровня 2, а набор «abac», «abab», «ba» – уровня 3, поскольку наибольший общий префикс слов «abac» и «abab» имеет длину 3.

Задача, которую профессор де Фрошин поставил своим студентам, заключается в следующем: по заданному набору слов и числу k требуется выбрать из заданных слов максимальный набор, который является почти беспрефиксным кодом уровня k. А вас он просит написать программу для помощи в проверке ответов.

Формат входного файла

Первая строка входного файла содержит два целых числа: n и k – количество слов в заданном наборе и уровень почти беспрефиксного кода, который требуется построить. Следующие n строк содержат по одному слову. Слова состоят из строчных букв латинского алфавита. Длина каждого слова от 1 до 200 символов. Суммарная длина всех слов не превышает 106. Все слова различны.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 100 000

0 ≤ k ≤ 200

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
6 2
aba
bacaba
abacaba
baca
abac
caba
3
aba
bacaba
caba

0.100s 0.018s 15