Description

Little A wants to build a very large tree, but his materials are limited, so he uses a small trick. Initially, Little A has a tree with $N$ nodes, numbered $1, 2, ..., N$, where node $1$ is the root; we call this the "template tree". Little A decides to construct a large tree based on this template tree. The construction proceeds as follows:

1. Copy the template tree as the initial large tree.

2. Repeat steps (2.1)–(2.3) $M$ times.

(2.1) Choose two integers $a, b$, where $1 \leq a \leq N$, $1 \leq b \leq$ the current number of nodes in the large tree.

(2.2) Copy the subtree of the template tree rooted at node $a$, and attach it under node $b$ in the large tree (that is, after copying, the subtree rooted at node $a$ from the template tree becomes a subtree of node $b$ in the large tree).

(2.3) Renumber the newly added nodes in the large tree according to their order in the template tree. For example, suppose the large tree has $L$ nodes before step (2.2), and the subtree rooted at $a$ in the template tree has $C$ nodes. Then the $C$ newly added nodes will be numbered $L+1, L+2, ..., L+C$ in the large tree; the relative order of these $C$ node numbers in the large tree is consistent with the order of the corresponding $C$ nodes in the template tree. An example is given below. Suppose the template tree is as follows:

According to step (1), the initial large tree is the same as the template tree.

In step (2.1), suppose we choose $a=4, b=3$. After performing steps (2.2) and (2.3), the new large tree is as shown below:

Now he asks you for the distances between some pairs of nodes in the tree.

Input Format

The first line contains three integers $N, M, Q$, separated by spaces, where $N$ is the number of nodes in the template tree, $M$ is the number of repetitions of the operation in step (2), and $Q$ is the number of queries.

The next $N-1$ lines each contain two integers $fr, to$, representing an edge in the template tree.

Then there are $M$ lines, each containing two integers $x, to$, representing one operation that copies the subtree rooted at $x$ in the template tree and attaches it as a subtree of node $to$ in the large tree.

Then there are $Q$ lines, each containing two integers $fr, to$, asking for the distance between nodes $fr$ and $to$ in the large tree.

$N, M, Q \leq 100000$.

Output Format

Output $Q$ lines, each containing one integer. The $i$-th line is the answer to the $i$-th query.

5 2 3
1 4
1 3
4 2
4 5
4 3
3 2
6 9
1 8
5 3

6
3
3

Hint

After two operations, the large tree becomes the shape shown below:

There are $6$ edges between nodes $6$ and $9$, so the distance is $6$. Similarly, there are $3$ edges between nodes $1$ and $8$. There are also $3$ edges between nodes $5$ and $3$.

Translated by ChatGPT 5