Regions#293

Regions

10 seconds

128 megabytes

Hard

The United Nations Regional Development Agency (UNRDA) has a well-defined organizational structure. It employs $n$ people, each coming from one of $r$ geographically distinct regions of the world. The employees are numbered from $1$ to $n$ in order of decreasing seniority, with employee number $1$ (the Chair) being the most senior. The regions are numbered from $1$ to $r$ in arbitrary order. Every employee except for the Chair has a single direct supervisor, who is always more senior than the employee they supervise.

We say that an employee $A$ is a manager of employee $B$ if and only if $A$ is $B$ 's supervisor, or $A$ is a manager of $B$ 's supervisor. Thus, for example, the Chair is a manager of any other employee. Clearly, no two employees can be each other's managers.

Recently, the United Nations Bureau of Investigations (UNBI) received complaints that the UNRDA structure favors some regions over others. To investigate this, the UNBI plans to implement a computer system that, given the supervision structure of the UNRDA, can answer queries of the following form: for two regions $r_{1}$ r_1 and $r_{2}$ r_2, how many pairs of employees $(e_{1}, e_{2})$ (e_1, e_2) are there such that employee $e_{1}$ e_1 comes from region $r_{1}$ r_1, employee $e_{2}$ e_2 comes from region $r_{2}$ r_2, and $e_{1}$ e_1 is a manager of $e_{2}$ e_2? Each query has two parameters: region numbers $r_{1}$ r_1 and $r_{2}$ r_2, and the result is a single integer: the number of different pairs $(e_{1}, e_{2})$ (e_1, e_2) satisfying these conditions.

Write a program that, given the regions of origin for all agency employees and the supervision chain, interactively answers queries in the described form.

Input

The first line contains three integers: the number of employees $n$ ( $1 \leq n \leq 200000$ 1 \le n \le 200\,000), the number of regions $r$ ( $1 \leq r \leq 25000$ 1 \le r \le 25\,000), and the number of queries $q$ ( $1 \leq q \leq 200000$ 1 \le q \le 200\,000), separated by spaces.

The next $n$ lines describe the $n$ agency employees by decreasing seniority. The $k$ -th line describes the employee with number $k$ . The first line (for the Chair) contains a single integer $H_{1}$ H_1 — the Chair's region. Each of the next $n - 1$ n-1 lines contains two integers separated by a space: $S_{k}$ S_k ( $1 \leq S_{k} < k$ 1 \le S_k < k, $2 \leq k \leq n$ 2 \le k \le n) — the supervisor number for employee $k$ , and $H_{k}$ H_k ( $1 \leq H_{k} \leq r$ 1 \le H_k \le r, $1 \leq k \leq n$ 1 \le k \le n) — the region of employee $k$ .

Interaction

After reading the input, your program must interactively read queries from standard input and write results to standard output. Each of the $q$ queries must be answered one at a time: your program must output the result for each query before reading the next query.

Each query appears on a separate line of input and consists of two integers — the region numbers $r_{1}$ r_1 and $r_{2}$ r_2, separated by a space.

The response to each query is a single integer on its own line — the number of pairs of employees $(e_{1}, e_{2})$ (e_1, e_2) such that $e_{1}$ e_1 comes from region $r_{1}$ r_1, $e_{2}$ e_2 comes from region $r_{2}$ r_2, and $e_{1}$ e_1 is a manager of $e_{2}$ e_2.

Examples

Example 1

Note

The test data will be such that the answer to any query will always be less than $1000000000$ 1\,000\,000\,000.