Confusing Login Names

Confusing Login Names#3199

3 seconds

64 megabytes

Medium

Meikyokan University is well known for its research and education in computer science. The university's computer center has advanced and secure computing resources, including supercomputers and many personal computers connected to the Internet.

One of the computer center's policies is to allow students to choose their own login names. Unfortunately, students tend to select similar login names, which often leads to mistakes when entering or specifying login names. These problems are burdensome for the computer center staff.

To prevent such issues, Dr. Choei Takano, chief manager of the computer center, decided to eliminate similar and confusing login names. For this purpose, Takano needs to develop a program that detects confusing login names.

Based on the following four operations on strings, the distance between two login names is defined as the minimum number of operations needed to transform one login name into the other:

1. Deleting a character at any position. 2. Inserting a character at any position. 3. Replacing a character at any position with another character. 4. Swapping two adjacent characters at any position.

For example, the distance between "omura" and "murai" is two, because the following sequence of operations transforms "omura" into "murai":

Another example: the distance between "akasan" and "kaason" is also two.

Takano decided that two login names with small distance are considered confusing and should be avoided.

Your task is to write a program that lists all pairs of confusing login names.

Note that the rules may combine in subtle ways. For instance, the distance between "ant" and "neat" is two.

Input

The input consists of multiple datasets. Each dataset is given in the following format:

$n$

$d$

$nam e_{1}$ name_1

$nam e_{2}$ name_2

$\dots$

$nam e_{n}$ name_n

The first integer $n$ is the number of login names. The next integer $d$ is positive. Two login names whose distance is less than or equal to $d$ are considered confusing. You may assume that $0 < n \leq 200$ 0 < n \leq 200 and $0 < d \leq 2$ 0 < d \leq 2. The $i$ -th student's login name is given as $nam e_{i}$ name_i, which consists of only lowercase letters, with a length less than $16$ . There are no duplicates in $nam e_{i}$ name_i ( $1 \leq i \leq n$ 1 \leq i \leq n).

The end of input is indicated by a line containing only the number $0$ .

Output

For each dataset, your program should output all pairs of confusing login names, one pair per line, followed by the total number of confusing pairs in the dataset.

In each pair, the two login names must be separated only by a comma ( $,$ ), and the login name that comes first alphabetically should be listed first. The list of confusing pairs for each dataset must be sorted as follows: for two pairs " $w_{1}, w_{2}$ w_1, w_2" and " $w_{3}, w_{4}$ w_3, w_4", if $w_{1}$ w_1 comes before $w_{3}$ w_3 alphabetically, or they are equal and $w_{2}$ w_2 comes before $w_{4}$ w_4, then " $w_{1}, w_{2}$ w_1, w_2" should appear before " $w_{3}, w_{4}$ w_3, w_4".

Examples

Example 1