Дерево — это связный неориентированный граф без циклов. Реберный кактус — связный неориентированный граф без петель и кратных ребер, в котором каждое ребро лежит не более чем на одном простом цикле.
У Васи есть реберный кактус, в котором каждое ребро покрашено в какой-то цвет.
Вася хочет убрать из кактуса минимальное число ребер так, чтобы получилось дерево. При этом Вася хочет, чтобы количество различных цветов среди оставшихся ребер было максимально. Помогите ему узнать, сколько различных цветов может остаться в графе.
Выходные данные
Выведите одно целое число — максимальное количество различных цветов, которое можно оставить в графе.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2 4
2 3 1
3 4 2
4 2 3
|
3
|
|
2
|
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
|