405751: GYM102059 A Coloring Roads

A. Coloring Roadstime limit per test4 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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

The city number $$$1$$$ is the capital. Initially all roads have no 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 all the roads on the unique path from $$$u$$$ to the capital in the color $$$c$$$. Even 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 for the second part of each query.Input

The first line of the input contains three integers $$$n,C,Q$$$ ($$$1\leq n,C,Q\leq 2\times 10^5$$$), separated by a single space, which are the number of cities in RUN-land, the number of possible colors, and the number of queries, respectively. Each of the next $$$n-1$$$ lines contains two integers $$$u,v$$$ ($$$1\leq u,v\leq n$$$) meaning that there is a bidirectional road directly connecting the cities numbered $$$u$$$ and $$$v$$$.

Each of the next $$$Q$$$ lines contains a query, which contains $$$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$$$)

Output

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

ExampleInput

6 5 5
1 3
2 3
1 4
6 3
5 2
5 1 3
6 2 2
2 3 1
4 4 1
1 5 0

Output

1
2
2
3
1

Note

The answer for the last query is $$$1$$$ since color $$$5$$$ is used in $$$0$$$ roads.