Chemin augmentant – Regional event 2017

Level 6

Énoncé

Joseph Marchand s'est levé de bon matin aujourd'hui, il décide d'aller faire un petit tour au parc du coin. Comme il a pas mal de temps devant lui, il cherche à parcourir le parc en empruntant un maximum de chemins.

Le parc est constitué de $N$ intersections et de $M$ chemins, empruntables dans les deux sens. Chaque chemin $i$ permet de relier exactement 2 intersections, et a pour longueur $l_i$.

Cependant, pour que l'appréciation du paysage soit meilleure à chaque nouveau chemin emprunté. Il décide de faire un tour dans lequel à chaque changement de chemin, la longueur du nouveau chemin soit strictement plus grande que celle du précédent.

Aide Joseph en déterminant le nombre maximal de chemins qu'il peut emprunter pour son tour, sachant qu'il peut entrer dans le parc à n'importe quelle intersection, et peut sortir également à n'importe laquelle.

Entrée

L'entrée comprendra plusieurs lignes :

  • La première ligne contiendra deux entiers $N$ et $M$, le nombre d'intersections du parc et le nombre de chemins. Les intersections sont numérotées à partir de 0.
  • $M$ lignes suivront. La i-ème d'entre-elles contiendra trois entiers $x_i$, $y_i$ et $l_i$, les deux intersections auxquelles est relié le i-ème chemin, ainsi que sa longueur.

Sortie

Vous afficherez un entier, le nombre maximal de chemins que peut emprunter Joseph pour satisfaire sa bonne appréciation du paysage.

Contraintes

  • $1 \le N \le 10\ 000$
  • $1 \le M \le \min\left (50\ 000, \displaystyle\frac{N\cdot (N - 1)}{2}\right)$
  • $0 \le x_i \le N - 1$
  • $0 \le y_i \le N - 1$
  • $1 \le l_i \le 10\ 000$

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

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

Submit your solution

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