Ölkənin Ürəyi#533
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. Ərazinin mürəkkəbliyi səbəbindən şə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 rəhbərliyi hər hansı bir şəhəri müdafiə etmək üçün müəyyən sayda qoşun, , tələb olunduğunu bilir. Şəhəri onun özündə yerləşən qoşunlarla, həmçinin arada heç bir şəhər olmadan birbaşa magistral yolla birləşdirilmiş digər şəhərlərin qoşunları ilə müdafiə etmək olar. Daha uzaq qoşunlar vaxtında çata bilmir. Həmçinin bilirlər ki, düşmən bir anda 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ə oluna bilər. Əgər bir şəhər müdafiə oluna bilməzsə, komandanlıq həmin şəhərdə olan qoşunların əsir düşəcəyini və Graphiyanın müdafiəsində istifadə oluna bilməyəcəyini qəbul etməli olacaq. Aşağıdakı nümunədə K=10 qəbul edək. şəhəri yaxşı müdafiə olunmuş kimi görünə bilər, amma nəticədə düşəcək.
Graphiya rəhbərliyi ölkənin Ü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 rəsmi şəkildə: bir şəhər özündən və ona birbaşa bitişik olan şəhərlərdən ən az qoşun toplaya bilirsə, müdafiə oluna bilər. Şəhərlər dəsti yalnız özündən və dəstdəki bitişik şəhərlərdən istifadə etməklə hər bir şəhərin müdafiə oluna bildiyi halda müdafiə oluna biləndir. Ölkənin Ürəyi — ən böyük müdafiə oluna bilən şəhərlər dəstidir, yəni heç bir başqa müdafiə oluna bilən dəst daha çox şəhəri əhatə etmir.
Bir neçə məlumat dəsti olacaq. Hər dəst iki tam ədəd — və — ilə başlayır, burada şəhərlərin sayıdır (3 \le N \le 1000), isə bir şəhərin müdafiəsi üçün tələb olunan qoşun sayıdır.
Şəhərlər -dan N-1-ə qədər nömrələnir.
Növbəti sətirdə şəhərlər təsvir olunur, -cı şəhərdən başlayaraq. Hər sətir həmin şəhərdə yerləşən qoşunların sayını göstərən tam ədədi ilə başlayır (0 \le T \le 10000). Bu, ardınca həmin şəhərdən çıxan magistral yolların sayını bildirən tam ədədi və ardından həmin magistralların getdiyi şəhərlərin sayda nömrəsi gəlir. Bir cüt şəhəri iki magistral yol birləşdirmir, buna görə siyahıdakı hər şəhər unikaldır. Heç bir magistral yol şəhərdən həmin şəhərə geri dönmür. Magistral yollar ikitərəflidir — əgər şəhəri -nin siyahısındadırsa, onda şəhəri də -nin siyahısında olacaq. Giriş iki boşluqla ayrılmış ilə bitəcək.
Hər bir məlumat dəsti üçün bir sətrdə iki tam ədəd çap edin: ölkənin ürəyindəki şəhərlərin sayı və oradakı qoşunların sayı. Tam ədədlər arasında bir boşluq qoyun. Çıxışlar arasında boş sətir olmamalıdır.
Nümunə 1