Arxiv ağacı#13102

Arxiv ağacı

1 saniyə
256 meqabayt

Arxiv -dən -ə qədər nömrələnmiş qovluqdan ibarətdir. Bəzi qovluq cütləri bilavasitə keçidlərlə bağlıdır, belə keçidlərin ümumi sayı n - 1-dir və istənilən qovluqdan keçidlər vasitəsilə istənilən digər qovluğa keçmək olar; başqa sözlə, qovluqlar və keçidlər ağac əmələ gətirir. qovluğu kök qovluqdur.

Hər bir v \ne s qovluğu üçün onun valideyn qovluğu -dən kök qovluğa gedən yolda -nin qonşusudur, isə öz valideyninin alt qovluğu adlanır.

Hər bir qovluğuna müsbət tam ədəd olan f_v adı verilməlidir. Arxivin qaydalarına görə adlar aşağıdakı şərtləri ödəməlidir:

Qısa adları yazmaq daha asandır, ona görə də administrator arxivdəki ən böyük adın mümkün qədər kiçik olmasını istəyir. \max\limits_{1 \le v \le n} f_v ifadəsinin mümkün minimal qiymətini tapın.

Giriş

Birinci sətirdə bir tam ədəd (1 \le t \le 5 \cdot 10^5) — test hallarının sayı verilir.

Hər test halının birinci sətrində iki tam ədəd və (1 \le s \le n \le 5 \cdot 10^5) — qovluqların sayı və kök qovluğun nömrəsi verilir. Sonrakı n - 1 sətrin hər birində iki tam ədəd və (1 \le u, v \le n, u \ne v) — keçidlə bağlanmış qovluqlar verilir. Zəmanət verilir ki, keçidlər ağac əmələ gətirir.

Bütün test halları üzrə qiymətlərinin cəmi 5 \cdot 10^5-i aşmır.

Çıxış

Hər test halı üçün bir tam ədəd — mümkün olan minimal ən böyük adı çap edin.

Nümunələr

Nümunə 1

Loading
Loading

Qeyd

Birinci test halında kök qovluq -dür və onun , və alt qovluqları var. qovluğunun və alt qovluqları, qovluğunun isə və alt qovluqları var. Adların optimal təyinatlarından biri belədir:

  • f_4 = 1;

  • f_1 = 1, f_2 = 2, f_8 = 3;

  • f_3 = 1, f_5 = 2;

  • f_6 = 2, f_7 = 4.

Göstərmək olar ki, ən böyük ad -dən kiçik ola bilməz.

İkinci test halında qovluqlar ortasında kök qovluğu olan 1 - 2 - 3 - 4 - 5 zənciri əmələ gətirir. və qovluqları kök qovluğun alt qovluqlarıdır, ona görə də onların adları fərqli olmalıdır. Məsələn, f_1 = f_2 = f_3 = 1 və f_4 = f_5 = 2, deməli cavab -dir.

Üçüncü test halında yalnız kök qovluq var və f_1 = 1.