Üç şəhər#1743
Bir ştatda şəhər var. Bəzi şəhərlər yollarla birləşdirilib və istənilən iki şəhər və üçün belə bir xüsusiyyət var: yalnız yollarla hərəkət edərək və eyni yoldan bir dəfədən artıq istifadə etməmək şərtilə şəhərindən şəhərinə getməyin məhz bir yolu var.
Bu ölkənin prezidenti son zamanlar belə bir sual maraq göstərib: hansı üç şəhər bir-birindən ən uzaqda yerləşir? Yəni, üç şəhərin — , və -nin qarşılıqlı uzaqlığı belə müəyyən edilir: öncə -dan -yə, sonra -dən -yə, ardınca isə -dən -ya getmək üçün istifadə olunacaq yolların sayının minimumu. (Bu halda, müxtəlif səyahətlərdə eyni yoldan istifadə etmək olar.)
Tapşırıq: üç elə şəhər tapmaq lazımdır ki, onların qarşılıqlı uzaqlığı maksimum olsun.
Məsələn, şəkildə 1 göstərilmiş beş şəhər üçün ən uzaqda yerləşən üç şəhər , və -dir (qarşılıqlı uzaqlıq 2 + 3 + 3 = 8-dir), şəkil 2-də isə istənilən üç şəhər \{1, 2, 4, 5\} çoxluğundan seçilə bilər (uzaqlıq 2 + 2 + 2 = 6).
Birinci sətrdə — şəhərlərin sayı verilir (3 \leq N \leq 1000). Növbəti sətrdə şəhərlərin təsviri verilir. -ci şəhərin təsviri əvvəlcə K_i — onun yollarla birləşdiyi şəhərlərin sayı (1 \leq K_i \leq N), sonra isə K_i ədəd - birləşdiyi şəhərlərin nömrələri ilə verilir.
Zəmanət verilir ki, giriş məlumatları düzgündür: əgər şəhərindən şəhərinə yol varsa, deməli, -dən -ya da yol var və bütün şəhər cütləri üçün problemlə verilmiş xüsusiyyət ödənir.
Üç müxtəlif ədəd çıxış edin — ən uzaqda yerləşən üç şəhərin nömrələri (istənilən ardıcıllıqda). Bir neçə cavab mümkündürsə, istənilən birini çap edin.
Nümunə 1