서울과학고등학교 쪼개기

서울의 명소 서울과학고등학교에는 1부터 $N$까지 번호가 매겨진 건물이 $N - 1$개의 길로 연결되어 있다. 서울과학고등학교는 어떤 두 건물 사이도 연결된 길만으로 오갈 수 있다. 다음은 유효한 서울과학고등학교이다.

정후는 서울과학고등학교를 여러 조각으로 분열시킨 뒤 이곳을 지배할 계획을 세우고 있다. 각 길은 $M$개의 색 중 정확히 하나로 칠해져 있으며, 정확히 하나의 조각에 속한다. 한 건물을 공유하는 두 길이 같은 색으로 칠해져 있으면 두 길은 연결되어 있다. 연결된 길은 같은 조각에 속하고, 연결되지 않은 길은 다른 조각에 속하도록 조각을 나눈다. 다음 서울과학고등학교는 정확히 세 개의 조각으로 쪼개진다.

정후는 서울과학고등학교에 심어 둔 스파이에게 명령해 길에 색을 $Q$번 새로 칠하게 한다. 길을 새로 칠할 때마다 서울과학고등학교가 정확히 몇 개의 조각으로 나뉘는지 알려 주자.

길의 색을 새로 칠할 때 새 색이 이전 색과 같을 수 있음에 주의하라. 새로 칠한 길은 그 길에 다시 새로운 색이 칠해지기 전까지 지워지지 않는다.

첫째 줄에 세 정수 $N$, $M$, $Q$가 공백으로 구분되어 주어진다. 둘째 줄부터 $N$째 줄까지 $N - 1$개의 줄에 세 정수 $u_i$, $v_i$, $w_i$가 공백으로 구분되어 주어진다. 이는 색 $w_i$로 칠해진 $i$번 길이 $u_i$번 건물과 $v_i$번 건물을 연결한다는 뜻이다. $N + 1$째 줄부터 $N + Q$째 줄까지 $Q$개의 줄에 두 정수 $p_i$, $t_i$가 공백으로 구분되어 주어진다. 이는 $p_i$번 길을 색 $t_i$로 칠하라는 명령이다.

$Q$개의 줄에 걸쳐 $i$번째 줄에는 $i$번째 명령을 처리한 뒤의 조각 개수를 나타내는 정수 하나를 출력한다.

• 2 ≤ $N$, $M$ ≤ 200,000
• 1 ≤ $Q$ ≤ 100,000
• 1 ≤ $u_i$ < $v_i$ ≤ $N$
• 1 ≤ $w_i$, $t_i$ ≤ $M$
• $i \neq j$이면 $u_i \neq u_j$ 또는 $v_i \neq v_j$이다.
• 1 ≤ $p_i$ ≤ $N - 1$
• 주어지는 모든 수는 정수이다.

이 문제를 풀어서 서울과학고등학교를 쪼개 버리자.