El doctor OCI-Cub y sus colegas han estado trabajando sin descanso para controlar la propagación de la terrible enfermedad humana COVID-19 en su pais de misión internacionalista. Juntos, supervisan una relaión de ~N~ aldeas convenientemente numeradas del ~1~ al ~N~. Las aldeas están conectadas por un conjunto de ~N-1~ caminos de tal manera que cualquier aldea puede ser alcanzada desde la aldea ~1~ por medio de una secuencia de caminos.

Desafortunadamente, un paciente en la aldea ~1~ acaba de dar positivo por COVID-19. Ninguna de los otros pacientes en esa aldea o en cualquier otra aldea tiene la enfermedad todavía. Sin embargo, sabiendo la naturaleza contagiosa de la enfermedad, el doctor OCI=Cub anticipa que exactamente uno de los siguientes eventos adversos sucederá en cada día sucesivo:

1. En una sola aldea, un evento de "supercontagio" hace que el número de pacientes en esa aldea con COVID-19 se duplique; o

2. Una solo paciente con COVID-19 se mueve a lo largo de un camino desde una aldea a una aldea adyacente.

Tarea

El doctor OCI_Cub está preocupado por lo rápido que podría propagarse el brote. Ayúdalo determinando el número mínimo posible de días antes de que pueda ser el caso de que al menos un paciente en cada aldea tenga la enfermedad.

Entrada

La primera línea contiene el entero ~N~.

Las siguientes ~N-1~ líneas contienen cada una dos enteros ~a~ y ~b~ separados por un espacio, describiendo un camino entre las aldeas ~a~ y ~b~. Ambos, ~a~ y ~b~, están en el rango ~1...N~.

Salida

El número mínimo de días hasta que el brote pueda alcanzar todas las aldeas.

Restricciones

~1 \le N \le 10^5~

Subtareas

• Casos 1-4: Cada aldea está conectada directamente a la aldea 1 (excepto la aldea 1).
• Casos 5-7: Las aldeas ~2...N~ están cada una adyacente a lo más dos caminos.
• Casos 8-15: Sin restricciones adicionales.

Ejemplo de Entrada

4
1 2
1 3
1 4

Ejemplo de Salida

5

Una posible secuencia de eventos correspondientes a este ejemplo es la siguiente: el número de pacientes enfermos en la aldea 1 se duplica y luego vuelve a duplicarse, de modo que después de dos días, hay 4 pacientes enfermos en la aldea 1. En cada uno de los siguientes 3 días, un paciente enfermo viaja desde la aldea 1 a cada una de las aldeas 2, 3 y 4 respectivamente. Después de 5 días, al menos 1 paciente enfermo existe en cada aldea.