Assemblage de branches – Regional event 2017

Level 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$

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
7 5
0 1
1 2
3 4
4 5
4 6
Sample output
4
Note

Cet exemple correspond à l'image ci-dessus.

Sample input
10 7
0 1
2 3
2 4
2 5
4 6
7 8
8 9
Sample output
6

Submit your solution

You have to register or log in to be able to submit your solution.