Заплутані імена для входу#3199

Заплутані імена для входу

3 секунди

64 мегабайти

Середня

Університет Мейкьокан відомий своїми дослідженнями й освітою в галузі інформатики. Комп'ютерний центр університету має сучасні й безпечні обчислювальні ресурси, включаючи суперкомп'ютери та багато персональних комп'ютерів, підключених до Інтернету.

Одна з політик комп'ютерного центру дозволяє студентам вибирати власні імена для входу. На жаль, студенти часто обирають схожі імена для входу, що часто призводить до помилок під час введення або вказування імен. Ці проблеми створюють додаткове навантаження для працівників комп'ютерного центру.

Щоб запобігти таким проблемам, доктор Чоей Такано, головний менеджер комп'ютерного центру, вирішив усунути схожі й заплутані імена для входу. Для цього Такано потрібно розробити програму, яка виявляє заплутані імена для входу.

Відстань між двома іменами для входу визначається як мінімальна кількість операцій, необхідна для перетворення одного імені на інше, на основі наступних чотирьох операцій над рядками:

1. Видалення символу в будь-якій позиції. 2. Вставка символу в будь-якій позиції. 3. Заміна символу в будь-якій позиції на інший символ. 4. Обмін місцями двох сусідніх символів у будь-якій позиції.

Наприклад, відстань між "omura" та "murai" дорівнює двом, оскільки наступна послідовність операцій перетворює "omura" на "murai":

Ще один приклад: відстань між "akasan" та "kaason" також дорівнює двом.

Такано вирішив, що два імена для входу з малою відстанню вважаються заплутаними й їх слід уникати.

Ваше завдання — написати програму, яка знаходить усі пари заплутаних імен для входу.

Зверніть увагу, що правила можуть поєднуватись складним чином. Наприклад, відстань між "ant" та "neat" дорівнює двом.

Вхідні дані

Вхід складається з кількох наборів даних. Кожен набір задано у такому форматі:

$n$

$d$

$nam e_{1}$ name_1

$nam e_{2}$ name_2

$\dots$

$nam e_{n}$ name_n

Першим іде ціле число $n$ — кількість імен для входу. Далі слідує ціле число $d$ . Два імені вважаються заплутаними, якщо їхня відстань не більша за $d$ . Відомо, що $0 < n \leq 200$ 0 < n \leq 200 і $0 < d \leq 2$ 0 < d \leq 2. $i$ -те ім'я для входу задано як $nam e_{i}$ name_i (складається лише з малих латинських літер, довжина — менше $16$ ). Усі імена $nam e_{i}$ name_i різні ( $1 \leq i \leq n$ 1 \leq i \leq n).

Кінець вхідних даних позначається рядком, що містить лише число $0$ .

Вихідні дані

Для кожного набору даних ваша програма повинна вивести усі пари заплутаних імен для входу, по одному рядку на пару, а наприкінці — загальну кількість заплутаних пар у наборі.

У кожній парі два імені мають бути розділені лише комою ( $,$ ), і ім'я, яке лексикографічно менше, повинно бути першим. Список пар заплутаних імен для кожного набору необхідно впорядкувати таким чином: для двох пар " $w_{1}, w_{2}$ w_1, w_2" та " $w_{3}, w_{4}$ w_3, w_4", якщо $w_{1}$ w_1 йде раніше за $w_{3}$ w_3 лексикографічно, або вони рівні і $w_{2}$ w_2 йде раніше за $w_{4}$ w_4, то " $w_{1}, w_{2}$ w_1, w_2" повинна бути раніше " $w_{3}, w_{4}$ w_3, w_4".

Приклади

Приклад 1