Assemblage de branches – Épreuve régionale 2017

Niveau 5

Énoncé

Joseph Marchand s'aventure dans un parc près de sa maison de vacances. Il se trouve au milieu du parc un arbre très ancien. Joseph peut observer un amas de branches tombées au pied de l'arbre. Étant fan de construction, il se demande s'il ne peut pas assembler ces branches de manière à obtenir la plus longue branche possible.

Une branche consiste en une extrémité racine (là où elle a été coupée de l'arbre) et en sous-branches reliées à la racine par un segment de longueur unitaire. Une sous-branche peut être soit encore une branche, soit une autre extrémité.

Pour commencer, Joseph a numéroté chaque point des branches, en commençant à partir de 0, dont part au moins un segment. Il vous donne ensuite la liste des branches par une succession de paires de points $(x, y)$, qui signifie que les points $x$ et $y$ sont reliés directement par un segment.

Assembler deux branches distinctes consiste à fusionner deux points, l'un appartenant à la première branche, l'autre à la deuxième. Il en résulte une nouvelle branche.

exemple.png

La longueur d'une branche est la distance la plus longue entre deux de ses extrémités. Par exemple, la longueur de la branche suivante est 4 :

ex2.png

Entrée

L'entrée comprendra plusieurs lignes :

  • La première ligne contiendra deux entiers $N$ et $M$, le nombre de points numérotés et le nombre de paires de points formant une arête.
  • Les M lignes suivantes contiennent chacune 2 entiers $x$ et $y$, signifiant que les points $x$ et $y$ sont directement reliés par une arête.

Sortie

Vous afficherez un entier, la longueur maximale qu'il est possible d'obtenir en assemblant les branches.

Contraintes

  • $1 \le N \le 1\ 000$
  • $1 \le M \le N - 1$
  • $0 \le x, y \le N - 1$

Contraintes de performance

  • $1 \le N \le 100\ 000$

Contraintes d'exécution

Utilisation mémoire maximum
10000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
7 5
0 1
1 2
3 4
4 5
4 6
Exemple de sortie
4
Commentaire

Cet exemple correspond à l'image ci-dessus.

Exemple d'entrée
10 7
0 1
2 3
2 4
2 5
4 6
7 8
8 9
Exemple de sortie
6