Kaçak İnek (Platin)#10427
Sonunda köşeye sıkıştırılan Bessie, uzak bir çiftlikte yer altına saklandı. Çiftlik ahırdan ve bunlar arasındaki n - 1 çift yönlü tünelden oluşur; öyle ki her ahır çifti arasında tek bir yol vardır. Yalnızca bir tüneli olan her ahır bir çıkıştır. Sabah olduğunda Bessie ahırlardan birinde yüzeye çıkacak ve bir çıkışa ulaşmaya çalışacak.
Ancak Bessie bir ahırda yüzeye çıktığı anda, kolluk kuvvetleri onun yerini tam olarak belirleyebilecek. Ardından bazı çiftçiler farklı çıkış ahırlarından yola çıkacak ve Bessie'yi yakalamaya çalışacak. Çiftçiler Bessie ile aynı hızda hareket eder; yani her zaman biriminde her çiftçi bir ahırdan komşu bir ahıra geçebilir. Çiftçiler Bessie'nin her an nerede olduğunu bilir, Bessie de çiftçilerin her an nerede olduğunu bilir. Herhangi bir anda bir çiftçi Bessie ile aynı ahırdaysa ya da onunla aynı tünelden geçiyorsa, çiftçiler Bessie'yi yakalamış olur. Buna karşılık, Bessie herhangi bir çiftçi onu yakalamadan kesinlikle önce bir çıkış ahırına ulaşırsa kaçmayı başarır.
Bessie hangi ahırda yüzeye çıkması gerektiğinden emin değil. ahırın her biri için, çiftçilerin çıkış ahırlarına en uygun şekilde yerleştiğini varsayarak, Bessie orada yüzeye çıkarsa onu yakalamak için gereken en az çiftçi sayısını belirlemesine yardım edin.
İlk satırda bir tam sayı n~(2 \le n \le 7 \cdot 10^4) verilir. Sonraki n - 1 satırın her birinde, a_i ve b_i ahırları arasındaki bir tüneli tanımlayan iki tam sayı a_i ve b_i~(1 \le a_i, b_i \le n) bulunur.
satır yazdırın. -inci satırda, Bessie numaralı ahırda yüzeye çıkarsa onu yakalamak için gereken en az çiftçi sayısı yer almalıdır.
Örnek 1