Çaşdırıcı giriş adları#3199
Meikyokan Universiteti kompüter elmələri sahəsində tədqiqat və təhsil üzrə tanınmışdır. Universitetin kompüter mərkəzində superkompütterlər və İnterenetə qoşulmuş çoxlu fərdi kompütterlər daxil olmaqla, qabaqcıl və təhlükəsiz hesablama resursları mövcuddur.
Kompüter mərkəzinin siyəsətlərindən biri tələbələrə öz giriş adlarını seçmək imkanı verməkdir. Təəssüf ki, tələbələr bənzər giriş adları seçirlər, bu da giriş adlarını daxil edərkən və ya göstərərkən tez-tez səhvlərə gətirib çıxarır. Bu cür problemlər kompüter mərkəzinin işçiləri üçün əlverisşsizdir.
Bu problemlərin qarşısını almaq üçün kompüter mərkəzinin baş meneceri doktor Çoi Takano oxşar və çaşdırıcı giriş adlarını aradan qaldırmaq qərarına gəldi. Bu məqsədlə Takano çaşdırıcı giriş adlarını aşkar edən proqram hazırlamalıdır.
Sətirlər üzərində aşağıdakı dörd əməliyyata əsasən, iki giriş adı arasındakı məsafə bir giriş adını digərinə çevrimək üçün lazım olan minimum əməliyyatların sayıdır:
1. İstənilən mövedə bir simvolun silinməsi. 2. İstənilən mövedə bir simvolun əlavə edilməsi. 3. İstənilən mövedə bir simvolun başqa bir simvolla əvəz edilməsi. 4. İstənilən mövedə iki ardıcıl simvolun yerlərinin dəyişməsi.
Məsələn, "omura" və "murai" giriş adları arasındakı məsafə ikidir, çünkü aşağıdakı əməliyyatlar ardıcıllığı "omura"nı "murai"yə çevirir:
Başqa bir misal: "akasan" və "kaason" arasında da məsafə ikidir.
Takano qərara aldı ki, məsafəsi az olan iki giriş adı çaşdırıcı hesab ediləcək və onlardan çəkinmək lazımdır.
Sizin vəzifəniz bütün çaşdırıcı giriş adı cütlərini sadalayan proqram yazmaqdır.
Qeyd edək ki, qaydalar bəzən incə şəkildə birləşə bilər. Məsələn, "ant" və "neat" arasındakı məsafə ikidir.
Giriş bir neçə datasetdən ibarətdir. Hər dataset aşağıdakı formatdadır:
name_1
name_2
name_n
Birinci tam ədəd giriş adlarının sayıdır. Sonra gələn tam ədəd müsbətdir. Məsafəsi -dən kiçik və ya bərabər olan iki giriş adı çaşdırıcı hesab edilir. Verilir ki, 0 < n \leq 200 və 0 < d \leq 2. -ci tələbənin giriş adı name_i yalnız kiçik hərflərdən ibarətdir, uzunluğu -dan azdır. name_i-lər arasında təkrar yoxdur (1 \leq i \leq n).
Daxilolmanın sonu yalnız bir olan sətrlə müəyyən olunur.
Hər dataset üçün bütün çaşdırıcı giriş adı cütlərini, hər sətirdə bir cüt olmaqla, ardınca datasetsədəki ümumi çaşdırıcı cütlərin sayını çap edin.
Hər cütdə iki giriş adı yalnız vergül () ilə ayrılmalıdır və əlifba sırası ilə birinci gələn ad əvvəl yazılmalıdır. Hər dataset üçün çaşdırıcı cütlərin siyahısı belə sıralanmalıdır: iki cüt "w_1, w_2" və "w_3, w_4" üçün, əgər w_1 əlifba sırası ilə w_3-dən əvvəl gəlirsə və ya onlar bərabərdirsə və w_2 w_4-dən əvvəl gəlirsə, o zaman "w_1, w_2" "w_3, w_4"-dən əvvəl çıxmalıdır.
Nümunə 1