Coloring Roads

In RUN-land there are $n$ cities numbered $1$ to $n$. Some pairs of cities are connected by a bidirectional road. There are $n-1$ roads in total, and for any two cities there is a unique path from one to the other.

City $1$ is the capital. Initially no road has a color. Alex, the king of RUN-land, asks you to perform the following query $Q$ times.

• $u\ c\ m$: Given a city $u$, a color $c$, and an integer $m$, color every road on the unique path from $u$ to the capital in color $c$. If a road already has a color, change its color to $c$. After coloring, compute the number of colors in which exactly $m$ roads are colored.

Given $Q$ queries in total, compute the answer to the second part of each query.

The first line of the input contains three integers $n,\ C,\ Q$ ($1\leq n,\ C,\ Q\leq 200,000$), separated by a single space: the number of cities in RUN-land, the number of possible colors, and the number of queries.

Each of the next $n-1$ lines contains two integers $u,\ v$ ($1\leq u,\ v\leq n$), meaning that a bidirectional road directly connects the cities numbered $u$ and $v$.

Each of the next $Q$ lines contains a query, which consists of $3$ integers $u,\ c,\ m$ as described in the statement. ($1\leq u\leq n$, $1\leq c\leq C$, $0\leq m\leq n-1$)

Print $Q$ lines, one for each query. Each line must contain one integer, the answer to the corresponding query.