Yaşamaq vaxtı

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.

Giriş verilənləri

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 $0$-dan $n-1$-ə qədər nömrələnmişdir. Növbəti $n-1$ sətirin hər biri kompüterlər $a$ və $b(0\le a,b<n)$ arasında ikitərəfli əlaqəni təsvir edir.

Çıxış verilənləri

Hər bir test üçün optimal YM dəyərini ayrı sətirdə çıxarın.

Nümunələr