Çaşdırıcı Giriş Adları
Meikyokan Universiteti kompüter elmi sahəsində tədqiqat və təhsil sahəsində çox tanınır. Bu universitetin superkompüterlər və İnternetə qoşulmuş bir çox fərdi kompüterlər daxil olmaqla, qabaqcıl və təhlükəsiz hesablama imkanlarına malik kompüter mərkəzi var.
Kompüter mərkəzinin siyasətlərindən biri tələbələrə öz giriş adlarını seçməyə imkan verməkdir. Təəssüf ki, tələbələr oxşar giriş adlarını seçməyə meyllidirlər və bu, giriş adlarının daxil edilməsində və ya göstərilməsində səhvlərə səbəb olur. Bu problemlər kompüter mərkəzinin işçiləri üçün əlavə iş yükü yaradır.
Bu cür problemlərin qarşısını almaq üçün kompüter mərkəzinin baş meneceri Dr. Choei Takano oxşar və çaşdırıcı giriş adlarını aradan qaldırmağa qərar verdi. 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 əsaslanaraq, iki giriş adı arasındakı məsafə bir giriş adını digərinə çevirmək üçün lazım olan minimum əməliyyat sayıdır:
İstənilən mövqedəki bir simvolu silmək.
İstənilən mövqeyə bir simvol əlavə etmək.
İstənilən mövqedəki bir simvolu başqa bir simvolla əvəz etmək.
İstənilən mövqedəki iki bitişik simvolu dəyişdirmək.
Məsələn, "omura" və "murai" arasındakı məsafə ikidir, çünki aşağıdakı əməliyyatlar ardıcıllığı "omura"nı "murai"yə çevirir.
Başqa bir misal olaraq, "akasan" və "kaason" arasındakı məsafə də ikidir.
Takano kiçik məsafəli iki giriş adının çaşdırıcı olduğunu və buna görə də qarşısının alınmalı olduğunu qərara aldı.
Sizin işiniz bütün çaşdırıcı giriş adı cütlərini sadalayan bir proqram yazmaqdır.
Qaydaların incə yollarla birləşə biləcəyinə diqqət yetirin. Məsələn, "ant" və "neat" arasındakı məsafə ikidir.
Giriş verilənləri
Giriş bir neçə datasetdən ibarətdir. Hər bir dataset aşağıdakı formatda verilir:
n
d
name_1
name_2
...
name_n
Birinci tam ədəd n giriş adlarının sayını göstərir. Sonra müsbət tam ədəd d gəlir. Məsafəsi d və ya daha az olan iki giriş adı çaşdırıcı hesab olunur. Siz 0 < n ≤ 200 və 0 < d ≤ 2 olduğunu qəbul edə bilərsiniz. i-ci tələbənin giriş adı yalnız kiçik hərflərdən ibarət olan name[i] ilə verilir. Onun uzunluğu 16-dan azdır. name[i]-də təkrarlanmaların olmadığını qəbul edə bilərsiniz (1 ≤ i ≤ n).
Girişin sonu yalnız sıfırdan ibarət olan bir sətirlə göstərilir.
Çıxış verilənləri
Hər bir dataset üçün proqramınız çaşdırıcı giriş adı cütlərinin hamısını, hər sətirdə bir cüt olmaqla, datasetdəki çaşdırıcı cütlərin ümumi sayı ilə birlikdə çıxarmalıdır.
Hər bir cütdə iki giriş adı yalnız vergül simvolu (,) ilə ayrılmalıdır və əlifba sırası ilə birinci olan giriş adı digərindən əvvəl görünməlidir. Hər bir dataset üçün çaşdırıcı cütlərin bütün çıxışı aşağıdakı kimi sıralanmalıdır. "w1, w2" və "w3, w4" cütləri üçün, əgər w1 əlifba sırası ilə w3-dən əvvəl gəlirsə və ya onlar eynidirsə və w2 w4-dən əvvəl gəlirsə, o zaman "w1, w2" "w3, w4"-dən əvvəl görünməlidir.