Yaşamaq vaxtı#6552
Bildiyiniz kimi, əksər kompüter şəbəkələri ağac strukturuna malikdir, yəni hər bir kompüterdən digərinə yalnız bir yolla çatmaq mümkündür.
Yaşama Müddəti (YM) adlı parametr, şəbəkədə dolaşan məlumat paketinin hədəfə çatmadığı halda məhv ediləcəyi addımların sayını müəyyən edir. YM-nin məqsədi marşrutlaşdırma cədvəllərindəki səhvlərdən qaynaqlanan sonsuz dövranın qarşısını almaqdır.
Bir şəbəkəni digərinə birləşdirən marşrutlaşdırıcının yerləşdirilməsi optimal sayılır, əgər həmin marşrutlaşdırıcıdan eyni şəbəkədəki digər kompüterə göndərilən paketlər üçün lazım olan maksimum YM minimaldır. Verilən şəbəkə üçün, marşrutlaşdırıcı kimi istifadə ediləcək kompüteri özünüz seçə biləcəyiniz halda, maksimum YM dəyərini hesablamalısınız.
Birinci sətir testlərin sayını c~(1 \le c \le 100) ehtiva edir. Hər bir testin birinci sətiri şəbəkədəki kompüterlərin sayını n~(1 < n \le 10^5) ilə başlayır. Kompüterlər -dan n - 1-ə qədər nömrələnmişdir. Növbəti n - 1 sətirin hər biri kompüterlər və b~(0 \le a, b < n) arasında ikitərəfli əlaqəni təsvir edir.
Hər bir test üçün optimal YM dəyərini ayrı sətirdə çıxarın.
Nümunə 1