Prologin
2025
É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.
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 :
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$