Tehlikedeki İnek (Altın)#10424
Sonunda köşeye sıkıştırılan Bessie, uzak bir çiftlikte saklanmaktadır. Çiftlik, ahırdan ve aralarında bulunan n - 1 çift yönlü tünelden oluşmaktadır; ayrıca herhangi bir ahır çifti arasında yalnızca bir tek yol vardır. Yalnızca bir tünelin çıktığı her ahır bir çıkıştır. Sabah olduğunda, Bessie ahırlardan birinde yüzeye çıkacak ve bir çıkışa ulaşmaya çalışacaktır.
Ancak Bessie yüzeye çıkar çıkmaz, muhafızlar onun konumunu tam olarak belirleyebilecektir. Bunun üzerine çeşitli çıkış ahırlarından başlayan birkaç çiftçi harekete geçerek Bessie'yi yakalamaya çalışacaktır. Çiftçiler Bessie ile aynı hızda hareket ederler, yani her zaman biriminde her çiftçi bir ahırdan komşu bir ahıra geçebilir. Çiftçiler her an Bessie'nin nerede olduğunu bilir, Bessie de her an çiftçilerin nerede olduğunu bilir. Eğer herhangi bir anda çiftçilerden biri Bessie ile aynı ahırda bulunursa veya onunla aynı tünelden geçerse, çiftçiler Bessie'yi yakalamış olur. Aksi takdirde, eğer Bessie herhangi bir çiftçi tarafından yakalanmadan önce bir çıkış ahırına ulaşırsa kurtulmuş olur.
Bessie başarı şansından emin değildir, çünkü bu, muhafızların kaç çiftçiyi görevlendirebileceğine bağlıdır. Bessie'nin numaralı ahırda yüzeye çıkacağı bilinmektedir. Çiftçilerin çıkış ahırlarına en uygun şekilde dağılması durumunda, onu yakalamak için gereken minimum çiftçi sayısını belirlemesine yardımcı olun.
İlk satır ve k~(2 \le n \le 10^5, 1 \le k \le n) olmak üzere iki tam sayı içerir. Sonraki n - 1 satırın her biri, a_i ve b_i ahırları arasındaki tüneli tanımlayan a_i ve b_i~(1 \le a_i, b_i \le n) iki tam sayısını içerir.
Bessie'yi kesin olarak yakalamak için gereken minimum çiftçi sayısını yazdırın.
Örnek 1