Make a Forest

Time limit2sMemory limit512 MB

Summary

Given N weighted tuples (u,v,w) with distinct weights, build a forest realizing each tuple as a parent-child edge so that every internal node's parent edge is smaller than all its child edges, each node has at most M children, and the number of trees is minimized. Output that minimum tree count.

Level: Hard8 of 10
Topics: Graph, Union-find, Greedy, Sorting
Solved: No attempts yet

Problem

In 1736, Leonhard Euler wrote a paper on the Seven Bridges of Konigsberg, which is regarded as the first paper in the history of graph theory. Nowadays, the study of graph theory is considered very important, as shown by the fact that most discrete mathematics textbooks contain a chapter on graph theory.

This problem concerns graph theory, especially trees and forests. Given $N$ tuples $(u_i, v_i, w_i)$ , construct a forest with the minimum possible number of trees that satisfies all seven requirements below:

Each tree in the forest is a rooted tree.
Each node $x$ in the forest has a value $x.A$ .
Each edge $(x, y)$ in the forest has a value $(x, y).B$ .
Each tuple $(u_i, v_i, w_i)$ appears exactly once in the forest as a parent-child pair (parent node $p$ and child node $c$ ) with $u_i = p.A$ , $v_i = c.A$ , and $w_i = (p, c).B$ .
For every node $x$ that is neither the root nor a leaf, $(p, x).B$ is smaller than every $(x, c).B$ , where $p$ is the parent of $x$ and $c$ is a child of $x$ .
Every node in the forest has at most $M$ children.
The forest contains exactly $N$ edges.

To simplify the problem, all $w_i$ values are guaranteed to be distinct: no two tuples share the same $w_i$ .

Output the number of trees in such a forest whose number of trees is minimum.

Input

The first line contains two integers $N$ $M$ ( $1 \le N, M \le 100{,}000$ ), the number of tuples and the maximum number of children of each node in the forest. Each of the next $N$ lines contains three integers $u_i$ $v_i$ $w_i$ ( $1 \le u_i, v_i \le 2{,}000{,}000{,}000$ , $1 \le w_i \le N$ ), describing the tuple $(u_i, v_i, w_i)$ .

Output

Print one integer in a line: the number of trees in a forest with the minimum possible number of trees satisfying the given requirements.

Hint

Explanation for the 1st sample case:

For the first sample, this forest is the only forest satisfying all the requirements. It contains 2 trees.

On the other hand, this forest does not satisfy the requirements because:

Node $b$ violates requirement 5, since $(a,b).B = 3$ is larger than $(b,c).B = 1$ and $(b,d).B = 2$ .
Node $b$ violates requirement 6, since it has 3 children (note that $M$ is 2).
The forest has 6 edges while $N = 5$ (violating requirement 7).

Violating even one requirement already makes the forest invalid.

Examples3

Example 1
Input
```
5 2
2 4 3
4 4 5
4 7 1
7 2 4
4 8 2
```
Expected output
```
2
```
Example 2
Input
```
5 1
2 4 3
4 4 5
4 7 1
7 2 4
4 8 2
```
Expected output
```
3
```

Example 3

Input

5 10
1000 3000 3
2000 4000 5
1000 2000 1
3000 2000 4
2000 3000 2

Expected output