Almost prefix-free codes#4675
In coding theory, prefix-free codes are sets of words where no word is a prefix of another. For example, the set of words aba, aa, and bac is a prefix-free code, whereas the set abac, aba, ba is not, because aba is a prefix of abac.
Professor Deshifro, who works in a laboratory dedicated to the study of unnecessary information, is investigating his latest invention: almost prefix-free codes. A set of words is called an almost prefix-free code of level if, for any two words in the set, their longest common prefix is at most characters long. For example, the set abac, abc, ba is an almost prefix-free code of level , while the set abac, abab, ba is not, because the longest common prefix of abac and abab has length .
The latest task Professor Deshifro gave to his lab assistants is the following: given a set of words and a number , find the largest subset of the given words that forms an almost prefix-free code of level . As a junior lab assistant, your task is to write a program to solve this problem.
The first line contains two integers and (1 \leq n \leq 100\,000, 0 \leq k \leq 200) — the number of words in the set and the level of the almost prefix-free code to construct. The following lines each contain a word, consisting of lowercase Latin letters. Each word has length from to . The total length of all words does not exceed 10^6. All words are distinct.
Print the maximum number of words that can be selected from the given set to form an almost prefix-free code of level . Then print the selected words, one per line.
Example 1