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ök klasörün adı f_s = 1'dir;
diğer her klasörünün adı, onun ebeveyn klasörünün adının bir katıdır, yani bir pozitif tam sayı için f_v = k \cdot f_p (k = 1 durumuna izin verilir: bir alt klasör ebeveyniyle aynı ada sahip olabilir);
aynı klasörün iki alt klasörünün adları farklı olmalı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.
İ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.
Her test durumu için bir tam sayı — mümkün olan en küçük en büyük adı yazdırın.
Örnek 1
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.