Difusión de información
El Reino de Takahashi tiene ciudades, numeradas de a . Hay carreteras en este reino. La carretera i-ésima conecta la ciudad y la ciudad bidireccionalmente. Para dos ciudades cualesquiera y , es posible ir de la ciudad a la ciudad atravesando algunos caminos.
Takahashi, el rey, quiere difundir información por todo el reino. Dado que está ocupado, puede transmitir directamente esta información como máximo a pueblos.
Suponga que Takahashi termina de transmitir la información en el tiempo , entonces, para cada \(t = 1,2,3, ⋯\), sucede lo siguiente:
- Para cada par de ciudades y conectadas directamente por una carretera, si ya ha recibido la información en el tiempo pero no la ha recibido, la recibe en el tiempo .
Takahashi quiere elegir pueblos para transmitir la información tal que minimize el tiempo necesario hasta que cada todos los pueblos ya hayan recibido la información. Encuentre el tiempo mínimo que esto toma, o sea, el mínimo tiempo tal que si Takahashi selecciona óptimamente pueblos para difundir la información en el tiempo cero, en el tiempo ya todos los pueblos han recibido la información.
Restricciones
- Todos los valores de la entrada son números enteros.
- \(1\leK<N\le2×10^5\)
- \(1\leu_i,v_i\leN\)
- Para dos ciudades cualesquiera y , es posible ir de la ciudad a la ciudad atravesando algunos caminos.
Entrada:
La entrada se proporciona desde la entrada estándar en el siguiente formato:
N K
u[1] v[1]
u[2] v[2]
.
.
.
u[n-1] v[n-1]
Salida
Imprima la respuesta
Puntuación
- Para un 35% de los casos
- Para un 45% adicional
Ejemplos
Ejemplo de entrada 1
5 2
1 2
2 3
3 4
4 5
Ejemplo de salida 1
1
Si Takahashi transmite directamente la información al Pueblo 2 y 4, Los pueblos 1,2,3,4,5 la reciben en el momento 1,0,1,0,1, respectivamente. En este caso, la información se distribuye por todo el reino en el momento 1.
Podemos demostrar que este es el momento más temprano posible.
Ejemplo de entrada 2
5 1
1 2
1 3
1 4
5 4
Ejemplo de salida 2
2
Ejemplo de entrada 3
20 3
2 15
6 5
12 1
7 9
17 2
15 5
2 4
17 16
12 2
8 17
17 19
18 11
20 8
20 3
13 9
11 10
11 20
14 8
11 7
Ejemplo de salida 3
3
Comments