도로 색칠

RUN 나라에는 $1$번부터 $n$번까지 번호가 붙은 $n$개의 도시가 있다. 일부 도시 쌍은 양방향 도로로 연결되어 있다. 도로는 모두 $n-1$개이고, 임의의 두 도시 사이에는 유일한 경로가 존재한다.

$1$번 도시는 수도이다. 처음에 모든 도로에는 색이 없다. RUN 나라의 왕 Alex는 다음과 같은 질의를 $Q$번 수행하라고 한다.

• $u\ c\ m$: 도시 $u$, 색 $c$, 정수 $m$이 주어진다. $u$에서 수도까지의 유일한 경로에 있는 모든 도로를 색 $c$로 칠한다. 이미 색이 있는 도로도 색 $c$로 바꾼다. 색칠한 뒤, 정확히 $m$개의 도로가 칠해진 색의 개수를 구한다.

$Q$개의 질의가 주어질 때, 각 질의의 두 번째 부분에 대한 답을 구하라.

입력의 첫 줄에는 $n,\ C,\ Q$ ($1\leq n,\ C,\ Q\leq 200,000$)가 공백 하나를 사이에 두고 주어진다. 이는 각각 RUN 나라의 도시 수, 가능한 색의 수, 질의의 수이다. 다음 $n-1$개의 줄에는 두 정수 $u,\ v$ ($1\leq u,\ v\leq n$)가 주어지며, 이는 도시 $u$와 도시 $v$를 직접 연결하는 양방향 도로가 있음을 뜻한다.

다음 $Q$개의 줄에는 질의가 하나씩 주어진다. 각 질의는 문제에 설명된 대로 $3$개의 정수 $u,\ c,\ m$으로 이루어진다. ($1\leq u\leq n$, $1\leq c\leq C$, $0\leq m\leq n-1$)

$Q$개의 줄을 출력한다. 각 줄에는 해당 질의의 답을 나타내는 정수 하나를 출력한다.