Задания прошлых чемпионатов

"B" Кактусофобия / Финальный раунд RCC 2016
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

Дерево — это связный неориентированный граф без циклов. Реберный кактус — связный неориентированный граф без петель и кратных ребер, в котором каждое ребро лежит не более чем на одном простом цикле.

У Васи есть реберный кактус, в котором каждое ребро покрашено в какой-то цвет.

Вася хочет убрать из кактуса минимальное число ребер так, чтобы получилось дерево. При этом Вася хочет, чтобы количество различных цветов среди оставшихся ребер было максимально. Помогите ему узнать, сколько различных цветов может остаться в графе.

Формат входных данных

В первой строке дано два целых числа n, m (2 ≤ n ≤ 10 000) — количество вершин и ребер в графе Васи соответственно.

В следующих m строках дано по три целых числа u, v, c (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ c ≤ m) — вершины, которые соединяет очередное ребро, и его цвет. Гарантируется, что описанный граф является реберным кактусом.

Формат выходных данных

Выведите одно целое число — максимальное количество различных цветов, которое можно оставить в графе.

Примеры
Входные данные
4 4
1 2 4
2 3 1
3 4 2
4 2 3
Выходные данные
3
Входные данные
7 9
1 2 1
2 3 4
3 1 5
1 4 5
4 5 2
5 1 6
1 6 4
6 7 6
7 1 3
Выходные данные
6
 

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.