Fibre optique

Les élèves du lycée d'AlgoVille ont relié tous leurs ordinateurs à l'aide de cables réseaux. N'étant pas particulièrement fortunés, ils ont économisé sur le cable, et ont savament calculé la configuration optimale du réseau pour relier tout le monde à l'aide d'une longueur totale minimum de cable. Pour cela, ils ont utilisé un algorithme très efficace qu'ils ont simplement recopié du premier livre d'algorithmique venu. Tous les PC sont maintenant reliés entre eux et entre 2 PC donnés, il n'existe qu'une seule route possible pour les paquets.

Les élèves viennent de se cotiser pour s'abonner à un accès internet haut-débit par fibre optique, et se demandent où il serait judicieux de brancher l'arrivée de la fibre de manière à assurer une robustesse maximale au réseau. Ainsi, il faut que si par malheur un cable venait à se débrancher où que se soit, un maximum d'élèves continuent à avoir accès à internet. Et là les choses se corsent : le manuel du parfait petit algorithmicien ne contient aucun algorithme qui convienne... À vous de jouer !

• 1 <= N <= 100 000, où N est le nombre de PC du réseau. Notez qu'il y a donc N-1 cables dans ce réseau.

De plus, dans 30% des tests, N <= 1000.

La première ligne de l'entrée contient un seul entier : N, le nombre de PC.

Chacune des N-1 lignes suivantes décrit un cable et contient 2 entiers séparés par un espace : les numéros des deux PC que ce cable relie.

Les PC sont numérotés de 0 à N-1 inclus. Chaque cable n'est décrit qu'une seule fois.

Une fois que vous aurez déterminé sur quel PC il est judicieux de brancher la fibre optique, affichez le nombre maximum d'élèves qui pourraient être déconnectés d'internet si un cable entre 2 PC venait à être débranché.

10
1 8
3 4
8 3
2 3
2 6
7 6
5 6
5 9
6 0

5

Pour obtenir ce résultat, on branche la fibre sur le PC numéro 2. Quel que soit le cable que l'on débranche entre 2 PC, pas plus de 5 élèves peuvent être coupés du net en même temps.

Cette solution correspond à l'illustration donnée dans la description du sujet.

On pourrait également brancher la fibre optique sur le PC numéro 6, et obtenir le même résultat.