MOJ Round #2Ended |
El mapa de una ciudad está compuesto por $N$ intersecciones y $N - 1$ calles bidireccionales. Se sabe que no hay forma de salir de una intersección, pasar por una o más intersecciones (sin repetir ninguna) y finalmente volver a la intersección de la que se partió.
Se desea determinar cuál es la mayor cantidad de intersecciones donde se pueden instalar semáforos, garantizando que se cumpla que para todo par de intersecciones a lo sumo una tenga semáforo.
En la primera línea habrá un entero $N$ $(1 \leq N \leq 100000)$ indicando la cantidad de intersecciones de la ciudad.
En cada una de las siguientes $N - 1$ líneas habrá dos enteros separados por espacio $a$ y $b$, indicando que hay una calle bidireccional entre las intersecciones $a$ y $b$. Las intersecciones estarán numeradas desde $1$ hasta $N$.
Entero $M$ que indica la mayor cantidad de ciudades a las que se les pueden instalar semáforos.