숲 만들기

1736년, Leonhard Euler는 쾨니히스베르크의 다리 문제에 대한 논문을 썼으며, 이 논문은 그래프 이론 역사상 최초의 논문으로 여겨진다. 오늘날 그래프 이론은 매우 중요하게 다루어지며, 대부분의 이산수학 교재에는 그래프 이론에 대한 장이 포함되어 있다.

이 문제는 그래프 이론, 특히 트리와 포리스트에 관한 문제이다. $N$개의 튜플 $(u_i, v_i, w_i)$가 주어질 때, 다음 일곱 가지 조건을 모두 만족하는 포리스트 중에서 트리의 개수가 가장 적은 포리스트를 구성하라.

1. 포리스트의 각 트리는 루트가 있는 트리이다.
2. 포리스트의 각 노드 $x$는 값 $x.A$를 가진다.
3. 포리스트의 각 간선 $(x, y)$는 값 $(x, y).B$를 가진다.
4. 각 튜플 $(u_i, v_i, w_i)$는 부모 노드 $p$와 자식 노드 $c$ 사이의 부모 자식 관계로 포리스트에 정확히 한 번씩 등장하며, $u_i = p.A$, $v_i = c.A$, $w_i = (p, c).B$를 만족한다.
5. 루트도 리프도 아닌 모든 노드 $x$에 대해, $(p, x).B$는 모든 $(x, c).B$보다 작다. 여기서 $p$는 $x$의 부모이고 $c$는 $x$의 자식이다.
6. 포리스트의 모든 노드는 최대 $M$개의 자식을 가진다.
7. 포리스트는 정확히 $N$개의 간선을 포함한다.

문제를 단순화하기 위해, 모든 튜플의 $w_i$는 서로 다르다고 보장한다. 즉, 같은 $w_i$를 가진 두 튜플은 존재하지 않는다.

위 조건을 만족하면서 트리의 개수가 최소인 포리스트에 포함된 트리의 개수를 출력하라.

첫째 줄에 튜플의 개수와 각 노드가 가질 수 있는 최대 자식 수를 나타내는 두 정수 $N$ $M$ ($1 \le N, M \le 100{,}000$)이 주어진다. 다음 $N$개의 줄에는 각 튜플 $(u_i, v_i, w_i)$를 나타내는 세 정수 $u_i$ $v_i$ $w_i$ ($1 \le u_i, v_i \le 2{,}000{,}000{,}000$, $1 \le w_i \le N$)가 한 줄에 하나씩 주어진다. 같은 $w_i$를 가진 두 튜플은 존재하지 않음이 보장된다.

주어진 조건을 만족하면서 트리의 개수가 최소인 포리스트에 포함된 트리의 개수를 나타내는 정수를 한 줄에 출력한다.

첫 번째 샘플에 대한 설명은 다음과 같다.

첫 번째 샘플에서, 이 포리스트는 모든 조건을 만족하는 유일한 포리스트이다. 이 포리스트에는 2개의 트리가 있다.

반면에, 다음 포리스트는 조건을 만족하지 않는다.

1. 노드 $b$는 $(a,b).B = 3$이 $(b,c).B = 1$과 $(b,d).B = 2$보다 크므로 조건 5를 위반한다.
2. 노드 $b$는 3개의 자식을 가지므로 조건 6을 위반한다 ($M$은 2이다).
3. $N = 5$인데 포리스트에 6개의 간선이 있으므로 조건 7을 위반한다.

하나의 조건이라도 위반하면 해당 포리스트는 올바르지 않다.