Vaca en peligro (Oro)#10424
Acorralada finalmente, Bessie se ha escondido en una granja remota. La granja consta de graneros y n - 1 túneles bidireccionales entre ellos, de manera que entre cualquier par de graneros existe un único camino. Cada granero del que parte un solo túnel es una salida. Cuando llegue la mañana, Bessie aparecerá en la superficie en uno de los graneros e intentará llegar hasta una salida.
Sin embargo, tan pronto como Bessie salga a la superficie, los guardias del orden podrán determinar exactamente su ubicación. Entonces, varios granjeros comenzarán a moverse desde distintos graneros de salida e intentarán atrapar a Bessie. Los granjeros se mueven a la misma velocidad que Bessie, es decir, en cada unidad de tiempo cada granjero puede pasar de un granero a uno vecino. Los granjeros siempre saben dónde está Bessie, y Bessie siempre sabe dónde están los granjeros. Los granjeros atrapan a Bessie si en algún momento uno de los granjeros se encuentra en el mismo granero que ella, o recorre el mismo túnel que ella. Por el contrario, Bessie se salva si logra llegar a un granero de salida antes de que algún granjero la atrape.
Bessie no está segura de sus posibilidades de éxito, ya que estas dependen de cuántos granjeros puedan movilizar los guardias del orden. Se sabe que Bessie saldrá a la superficie en el granero . Ayúdala a determinar la cantidad mínima de granjeros necesaria para atraparla, suponiendo que los granjeros se distribuyan de manera óptima entre los graneros de salida.
La primera línea contiene dos números enteros y k~(2 \le n \le 10^5, 1 \le k \le n). Cada una de las siguientes n - 1 líneas contiene dos números enteros a_i y b_i~(1 \le a_i, b_i \le n), que describen un túnel entre los graneros a_i y b_i.
Muestra la cantidad mínima de granjeros necesaria para garantizar la captura de Bessie.
Ejemplo 1