Ölkənin Ürəyi
Graphiya milləti müharibə vəziyyətindədir. Qonşu millətlər uzun müddətdir ki, Graphiyanın çiçəklənən şəhərlər qurduğunu və onları magistral yollar şəbəkəsi ilə birləşdirdiyini qısqanclıqla izləyirdilər. İndi onlar da bu paydan bir parça istəyirlər.
Graphiya bir neçə şəhərdən ibarətdir və bu şəhərlər magistral yollarla birləşdirilib. Graphiyanın ərazisi çətindir, buna görə də şəhərlər arasında hərəkət etməyin yeganə yolu magistral yollardır. Hər bir şəhərdə müəyyən sayda qoşun yerləşdirilib. Graphiyanın hərbi komandanlığı bilir ki, hər hansı bir şəhəri müdafiə etmək üçün müəyyən sayda qoşun, K, tələb olunacaq. Onlar bir şəhəri orada yerləşdirilən qoşunlarla müdafiə edə bilərlər, birbaşa magistral yolla birləşdirilən digər şəhərlərdəki qoşunların dəstəyi ilə, arada heç bir şəhər olmadan. Daha uzaqda olan qoşunlar sadəcə vaxtında ora çata bilməzlər. Onlar həmçinin bilirlər ki, düşmənləri yalnız bir şəhərə hücum edəcək - beləliklə, bir şəhərdəki qoşunlar həm o şəhəri, həm də onun qonşularını müdafiə etmək üçün istifadə edilə bilər. Lakin, əgər bir şəhər müdafiə oluna bilməzsə, onda hərbi komandanlıq həmin şəhərdə yerləşdirilən qoşunların əsir götürüləcəyini və Graphiyanın müdafiəsinə kömək edə bilməyəcəyini qəbul etməlidir. Aşağıdakı halda, K = 10 olduğunu fərz edin. C şəhəri yaxşı müdafiə olunmuş kimi görünə bilər, lakin nəticədə düşəcək.
Graphiyanın rəhbərliyi ölkələrinin Ürəyini - bir-birini qarşılıqlı müdafiə edə biləcək ən böyük şəhərlər qrupunu müəyyən etmək istəyir, hətta digər bütün şəhərlər düşsə belə.
Daha dəqiq desək, bir şəhər özündən və ona birbaşa bitişik olan şəhərlərdən ən azı K qoşun toplaya bilirsə, müdafiə oluna bilər. Şəhərlər dəsti yalnız özündən və həmin dəstdəki bitişik şəhərlərdən qoşun istifadə edərək hər bir şəhərin müdafiə oluna bildiyi halda müdafiə oluna bilər. Ölkənin Ürəyi ən böyük müdafiə oluna bilən şəhərlər dəstidir - yəni, heç bir digər müdafiə oluna bilən şəhərlər dəsti ondan daha çox şəhərə malik deyil.
Giriş verilənləri
Bir neçə məlumat dəsti olacaq. Hər dəst iki tam ədədlə başlayır, N və K, burada N şəhərlərin sayıdır (3 <= N <= 1000), və K bir şəhəri müdafiə etmək üçün tələb olunan qoşunların sayıdır.
Şəhərlər 0 ilə N-1 arasında nömrələnib.
Növbəti N sətirdə şəhərlərin təsvirləri verilir, 0 şəhərindən başlayaraq. Hər bir şəhər təsviri sətiri həmin şəhərdə yerləşdirilən qoşunların sayını göstərən tam ədəd T ilə başlayır (0 <= T <= 10000). Bu, həmin şəhərdən çıxan magistral yolların sayını göstərən tam ədəd M ilə davam edir və sonra həmin magistral yolların getdiyi şəhərləri göstərən M tam ədəd gəlir. Eyni şəhərlərdən və şəhərlərə gedən iki magistral yol olmayacaq, beləliklə, hər bir siyahıdakı şəhərlər unikal olacaq. Heç bir magistral yol bir şəhərdən geri həmin şəhərə dövr etməyəcək. Magistral yollar hər iki istiqamətdə gedir, belə ki, əgər I şəhəri J şəhərinin siyahısındadırsa, onda J şəhərinin də I şəhərinin siyahısında olacağına zəmanət verilir. Giriş iki boşluqla ayrılmış 0 ilə bitəcək.
Çıxış verilənləri
Hər bir məlumat dəsti üçün bir sətirdə iki tam ədəd çap edin: ölkənin ürəyindəki şəhərlərin sayı və ölkənin ürəyindəki qoşunların sayı. Tam ədədlər arasında bir boşluq qoyun. Çıxışlar arasında boş sətir olmamalıdır.