In RUN-land, there are cities numbered to . Some pairs of cities are connected by a bidirectional road. It happens that there are roads in total and that for any two cities, and there is a unique path from one to the other.
The city number is the capital. Initially all roads have no color. Alex, the king of RUN-land asks you to perform the following query times.
: Given a city , a color , and an integer , color all the roads on the unique path from to the capital in the color . Even if a road already has a color, change its color to . After coloring, compute the number of colors in which exactly roads are colored.
Given queries in total, compute the answer for the second part of each query.
输入格式
The first line of the input contains three integers (), 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 lines contains two integers () meaning that there is a bidirectional road directly connecting the cities numbered and .
Each of the next lines contains a query, which contains integers as described in the statement. (, , )
输出格式
Print lines, one for each query. Each line must contain one integer, the answer to the corresponding query.
