|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||22||9||7||77.778%|
In 1736, Leonhard Euler wrote a paper on the Seven Bridges of Königsberg which is regarded as the first paper in the history of graph theory. Nowadays, the study of graph theory is considered very important as indicated by the fact that most textbooks in discrete mathematics have a chapter on graph theory.
This problem is related to graph theory, especially on tree and forest. Given N tuples (ui, vi, wi), your task is to construct a forest with a minimum number of trees which satisfies the following seven requirements:
To simplify the problem, it is guaranteed that wi in any tuple is unique, i.e. no two tuples with the same wi.
Output the number of trees in such forest (the forest should have the minimum number of trees).
The first line contains two integers: N M(1 ≤ N, M ≤ 100,000) in a line denoting the number of tuples and the maximum number of children for each node in the forest. The next N following lines, each contains three integers: ui vi wi (1 ≤ ui, vi ≤ 2,000,000,000; 1 ≤ wi ≤ N) in a line denoting the tuple (ui, vi, wi). It is guaranteed that there will be no two tuples with the same wi.
The output contains an integer denoting the number of trees in a forest with a minimum number of trees which satisfies the given requirements, in a line.
5 2 2 4 3 4 4 5 4 7 1 7 2 4 4 8 2
5 1 2 4 3 4 4 5 4 7 1 7 2 4 4 8 2
5 10 1000 3000 3 2000 4000 5 1000 2000 1 3000 2000 4 2000 3000 2
Explanation for the 1st sample case
For the first sample, this forest is the only forest which satisfies all the requirements. There are 2 trees in this forest.
On the other hand, this forest does not satisfy the requirements due to:
Note that violating even one requirement already makes the forest invalid.