Arşiv ağacı#13102

Arşiv ağacı

1 saniye
256 megabayt

Bir arşiv 'den 'ye kadar numaralandırılmış klasörden oluşur. Bazı klasör çiftleri doğrudan bağlantılarla bağlıdır, toplamda n - 1 bağlantı vardır ve herhangi bir klasörden bağlantılar üzerinden diğer herhangi bir klasöre ulaşılabilir; başka bir deyişle, klasörler ve bağlantılar bir ağaç oluşturur. klasörü kök klasördür.

Her v \ne s klasörü için, onun ebeveyn klasörü 'den kök klasöre giden yol üzerindeki 'nin komşusudur ve , ebeveyninin alt klasörü olarak adlandırılır.

Her klasörüne pozitif bir tam sayı olan f_v adı verilmelidir. Arşivin kurallarına göre adlar aşağıdaki koşulları sağlamalıdır:

Kısa adları yazmak daha kolaydır, bu yüzden yönetici arşivdeki en büyük adın mümkün olduğunca küçük olmasını istiyor. \max\limits_{1 \le v \le n} f_v ifadesinin mümkün olan en küçük değerini bulun.

Giriş

İlk satırda bir tam sayı (1 \le t \le 5 \cdot 10^5) — test durumlarının sayısı verilir.

Her test durumunun ilk satırında iki tam sayı ve (1 \le s \le n \le 5 \cdot 10^5) — klasörlerin sayısı ve kök klasörün numarası verilir. Sonraki n - 1 satırın her birinde iki tam sayı ve (1 \le u, v \le n, u \ne v) — bir bağlantıyla bağlanan klasörler verilir. Bağlantıların bir ağaç oluşturduğu garanti edilir.

Tüm test durumları üzerinden değerlerinin toplamı 5 \cdot 10^5'i aşmaz.

Çıktı

Her test durumu için bir tam sayı — mümkün olan en küçük en büyük adı yazdırın.

Örnekler

Örnek 1

Loading
Loading

Not

Birinci test durumunda kök klasör 'tür ve , ve alt klasörlerine sahiptir. klasörünün ve , klasörünün ise ve alt klasörleri vardır. Adların optimal atamalarından biri şudur:

  • f_4 = 1;

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

  • f_3 = 1, f_5 = 2;

  • f_6 = 2, f_7 = 4.

En büyük adın 'ten küçük olamayacağı gösterilebilir.

İkinci test durumunda klasörler, ortasında kök klasör bulunan 1 - 2 - 3 - 4 - 5 zincirini oluşturur. ve klasörleri kök klasörün alt klasörleridir, bu yüzden farklı adlara ihtiyaç duyarlar. Örneğin, f_1 = f_2 = f_3 = 1 ve f_4 = f_5 = 2, dolayısıyla cevap 'dir.

Üçüncü test durumunda yalnızca kök klasör vardır ve f_1 = 1.