Ulduzlar sistemi
Vədim astronomiyaya böyük maraq göstərir və astronomiya dərnəyinə də qatılır. Yaxınlarda dərnəkdə bürclər haqqında məlumat əldə etdi. Bu mövzu onu çox cəlb etdi və axşam evə qayıtdıqdan sonra teleskopla ulduzlu səmanı çəkdi, sonra isə şəkildən bürcləri axtarmağa başladı.
Bürcləri müəyyənləşdirmək üçün sadə bir qayda düşündü: Ulduz A şəkli "çox uzaqda olmayan" bütün ulduzlarla eyni bürcdədir. Ulduz A-dan ən yaxın ulduza olan məsafə d olaraq təyin edilir. Vədim, A ilə eyni bürcə, şəkilləri k·d məsafəsindən çox olmayan bütün ulduzları daxil edir, burada k Vədim tərəfindən əvvəlcədən seçilmiş tam ədəddir.
Bu qaydanı aşağıdakı şəkildə tətbiq edir. Vədimə görə, ulduzlar A və B eyni bürcdədirlər, əgər belə bir ulduzlar ardıcıllığı varsa: A = u_1, u_2, ..., u_l = B, burada ardıcıllıqda hər hansı iki qonşu ulduz u_i və u_{i+1} üçün aşağıdakı iki şərtdən ən az biri yerinə yetirilir:
Onların şəkilləri arasındakı məsafə k·md(u_i)-dən çox deyil (burada md(X) ulduz X-dən digər ulduza olan ən yaxın məsafəni göstərir);
Onların şəkilləri arasındakı məsafə k·md(u_{i+1})-dən çox deyil.
Bu halda, əgər göstərilən ulduzlar ardıcıllığı varsa, Vədim iki ulduzu mütləq eyni bürcə daxil edir.
Sizin vəzifəniz, Vədimin metoduna əsaslanaraq, şəkildəki ulduzların koordinatları haqqında məlumatdan istifadə edərək onları bürclərə ayıran bir proqram yazmaqdır.
Giriş verilənləri
Giriş faylının ilk sətiri iki tam ədəd ehtiva edir: n - şəkildəki ulduzların sayı (2 ≤ n ≤ 5000) və k (1 ≤ k ≤ 10). Növbəti n sətirin hər biri 2 ədəd ehtiva edir - x_i və y_i - növbəti ulduzun şəklinin koordinatları (|x_i|, |y_i| ≤ 10^5). Bütün ulduzların şəkilləri müxtəlif nöqtələrdə yerləşir.
Çıxış verilənləri
Çıxış faylında m - bürclərin sayını göstərin. Növbəti m sətirdə bürclərin təsvirlərini göstərin. Hər bürcün təsviri n_i - növbəti bürcdəki ulduzların sayı və n_i ədəd - bu ulduzların nömrələrini ehtiva etməlidir. Ulduzlar giriş faylında göstərilən ardıcıllıqla 1-dən n-ə qədər təbii ədədlərlə nömrələnir.