Split the SSHS

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

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

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

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

첫째 줄에 세 정수 N, M, 그리고 Q가 공백으로 구분되어 주어진다. 둘째 줄부터 N째 줄까지 N - 1 개의 줄에 세 정수 ui, vi, wi가 공백으로 구분되어 주어지며, 색 wi로 칠해진 i 번 길이 ui 번 건물과 vi 번 건물을 연결함을 나타낸다. N + 1째 줄부터 N + Q째 줄까지 Q 개의 줄에 두 정수 pi, ti가 공백으로 구분되어 주어지며, pi번 길을 색 ti로 색칠하라는 명령을 나타낸다.

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

• 2 ≤ N, M ≤ 200,000
• 1 ≤ Q ≤ 100,000
• 1 ≤ ui < vi ≤ N
• 1 ≤ wi, ti ≤ M
• i ≠ j이면 ui ≠ uj 또는 vi ≠ vj.
• 1 ≤ pi ≤ N - 1
• 주어지는 모든 수는 정수이다.

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