D - Viaje turístico

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Fito quiere hacer turismo por cierto país y está estudiando las ofertas de algunas agencias. El viaje está compuesto por $n$ atracciones de diverso tipo y Fito quiere visitarlas todas.

La compañía incluye en el plan el vuelo al primer lugar escogido por Fito, pero de ahí en adelante le corresponde a él moverse por el país. Por suerte en esa zona hay una red de transporte por tren gratuita. La red está compuesta por $n-1$ líneas que conectan pares de atracciones y se puede viajar entre cualquier par usando solo esta red. La razón de que el viaje en tren sea gratis es para promover el turismo, pero también hay otra razón menos noble. Al entrar en la zona turística se le entrega un documento que lo acredita como turista permitiéndole el uso gratuito del tren. Cada vez que un turista se monta en el tren solo debe enseñar dicho documento y puede viajar sin problemas. Sin embargo en cada viaje se añade al documento una marca indicando que se utilizó el tren. La parte negativa es que la primera vez que un turista llega a una atracción le cobran un impuesto por cada marca en su documento. La razón de esta medida es que los dueños de cada atracción quieren ser siempre los primeros en ser visitados y por tanto penalizan a los turistas según el tiempo que se demoran en llegar. En esta zona son muy celosos con las reglas y se cuidan mucho de trampas posibles, como viajar en tren sin marcar el documento o utilizar algún otro medio de transporte.

Fito está decidido a visitar todas las atracciones turísticas por lo que quiere saber el menor gasto, por concepto de impuestos, que le permita hacer esto.

Input

La primera línea de la entrada contiene un entero $n$ $(1 \leq n \leq 10^{6})$ representando la cantidad de atracciones que va visitar Fito. Las siguientes $n-1$ líneas describen los posibles viajes en tren, cada una con dos números enteros, separados por un espacio.

Output

La salida debe ser un número entero, que indica la menor cantidad de impuestos que debe pagar Fito si visita todas las atracciones.

Sample test(s)

Input
3 1 2 1 3
Output
3