Size 'den 'e kadar numaralandırılmış düğümlü bir ağaç veriliyor. İki düğüm arasındaki uzaklık, aralarındaki basit yol üzerindeki kenarların sayısıdır.
Boş olmayan bir düğüm kümesine, 'deki her iki düğüm için aralarındaki basit yol üzerindeki tüm düğümler de 'ye ait ise bağlantılı denir.
'den 'e kadar her için, 'deki herhangi iki düğüm arasındaki uzaklık en fazla olacak şekilde bağlantılı bir kümesinin en büyük boyutunu bulun.
İlk satırda bir tam sayı (1 \le t \le 5000) — test durumlarının sayısı verilir.
Her test durumunun ilk satırında bir tam sayı (1 \le n \le 5000) — düğümlerin sayısı verilir. Sonraki n - 1 satırın her biri iki tam sayı ve (1 \le u, v \le n, u \ne v) içerir — ve düğümleri arasındaki bir kenar. Kenarların bir ağaç oluşturduğu garanti edilir.
Tüm test durumları boyunca değerlerinin toplamı 'i aşmaz.
Her test durumu için tam sayı içeren bir satır yazdırın: bunlardan -incisi, herhangi iki düğüm arasındaki uzaklığın en fazla olduğu bağlantılı bir düğüm kümesinin en büyük boyutu olmalıdır.
Örnek 1
Birinci test durumunda ağacın düğümü vardır: numaralı düğüm , ve ile komşudur, numaralı düğüm ise , ve ile komşudur.
x = 1 için cevap 'dir, örneğin S = \{1, 3\}.
x = 2 için cevap 'tür, örneğin S = \{1, 3, 4, 5\}.
x = 3 için cevap 'tir, örneğin S = \{1, 3, 4, 5, 7\}: en büyük uzaklıklar ile arasında ve ile arasındadır ve bunlar 'e eşittir.
x \ge 4 için cevap 'dir, çünkü tüm düğümlerden oluşan kümenin en büyük uzaklığı 'tür.
İkinci test durumunda ağaç tek bir düğümden oluşur, bu yüzden cevap 'dir.
Üçüncü test durumunda ağaç 1 - 2 - 3 - 4 zinciridir. Bir zincirin düğümlü bağlantılı bir kümesinin en büyük uzaklığı k - 1'dir, bu yüzden x = 1, 2, 3, 4 için cevaplar 2, 3, 4, 4'tür.