|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Round #27Ended |
C - Enviando Mensajes
Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)
La Orden Inter-Galáctica ha descubierto una traición de alto nivel que necesita ser revelada lo antes posible y para difundir el mensaje ha decidido utilizar un nuevo mecanismo de transmisión. El reino Inter-Galáctico está formado por varias galaxias que están interconectadas entre ellas formando un grafo en forma de árbol, de manera tal que el Cuartel General de la Orden radica en la raíz y galaxia principal del reino. Las máquinas que transmitirán el mensaje solamente pueden enviarlo a una de las galaxias vecinas a la vez, demorándose un segundo en cada transmisión y se sabe que en cada galaxia del reino hay exactamente una máquina. Este mecanismo resulta especialmente eficiente si se escoge correctamente el orden en que se va a transmitir el mensaje a las galaxias vecinas. Tu tarea consiste en determinar cuál es el mínimo tiempo requerido para que el reino completo conozca la traición.
Input
Línea 1
: Un número entero $N$ $(1 \le N \le 200000)$ representando la cantidad de galaxias en el reino
Línea 2...N
: Dos enteros $X$ e $Y$ $(1 \le X, Y \le N, X \ne Y)$ indicando que las galaxias $X$ e $Y$ son vecinas en el reino.
nota
: El Cuartel General de la Orden Inter-Galáctica se encuentra en la galaxia 1.
Output
Línea 1
: Un entero indicando la cantidad mínima de segundos necesarios para difundir el mensaje por el reino.
Sample test(s)
Input
12
1 2
1 3
2 4
2 5
2 6
3 7
4 8
4 9
7 10
7 11
11 12
Output
5
Input
4
4 3
3 2
2 1
Output
3
Hints
Hint
En el primer ejemplo, estos son los pasos de una posible solución óptima
:
