Üç şəhər
Bir ölkədə N şəhər mövcuddur. Bəzi şəhərlər yollarla birləşdirilib və belə bir xüsusiyyət təmin edilib: hər hansı iki şəhər A və B arasında yalnız bir yol mövcuddur ki, bu yolla şəhər A-dan şəhər B-yə çatmaq mümkündür. Bu zaman yalnız yollardan istifadə etmək və eyni yoldan bir dəfədən çox keçməmək şərti var.
Bu ölkənin prezidenti maraqlanır: hansı üç şəhər bir-birindən ən uzaqdır? Yəni, üç şəhər A, B və C arasında qarşılıqlı uzaqlıq, A-dan B-yə, B-dən C-yə və C-dən A-ya getmək üçün lazım olan minimum yol sayıdır (bu zaman eyni yolu müxtəlif səyahətlərdə istifadə etmək mümkündür).
Məqsəd, bir-birindən qarşılıqlı uzaqlığı maksimum olan üç şəhəri tapmaqdır.
Məsələn, şəkildə 1-də göstərilən yollarla birləşdirilmiş beş şəhər üçün bir-birindən ən uzaq olan üç şəhər 1, 2 və 5 şəhərləridir (qarşılıqlı uzaqlıq 2 + 3 + 3 = 8-ə bərabərdir), şəkildə 2-dəki şəhərlər üçün isə {1, 2, 4, 5} çoxluğundan seçilmiş istənilən üç şəhərdir (uzaqlıq 2 + 2 + 2 = 6).
Giriş verilənləri
Giriş faylının birinci sətiri şəhərlərin sayı olan N ədədini ehtiva edir (3 ≤ N ≤ 1000). Sonrakı N sətir hər bir şəhərin təsvirini ehtiva edir. i-ci şəhərin təsviri əvvəlcə K_i – yollarla birləşdirildiyi şəhərlərin sayını (1 ≤ K_i < N), sonra isə yollarla birləşdirildiyi şəhərlərin nömrələrini ehtiva edir.
Giriş məlumatlarının düzgün olduğu, yəni əgər şəhər A-dan şəhər B-yə yol varsa, onda şəhər B-dən şəhər A-ya da yol olduğu və bütün şəhər cütləri üçün məsələnin şərtində göstərilən xüsusiyyətin yerinə yetirildiyi təmin edilir.
Çıxış verilənləri
Çıxış faylına bir-birindən ən uzaq olan üç şəhərin nömrələrini fərqli qaydada olmaqla çıxarın. Əgər bir neçə həll varsa, onlardan hər hansı birini çıxarın.