Large Tree Distance Queries

Little A wants to build a giant tree using clever tricks, although he only has a small amount of material. Initially, he has a template tree with \(N\) nodes, numbered \(1,2,\dots,N\) with node \(1\) as the root. He will build a large tree by copying subtrees of the template tree and attaching them to already existing nodes. The process is as follows:

1. Copy the template tree as the initial large tree.
2. Perform the following three steps exactly \(M\) times:
   1. Select two numbers \(a\) and \(b\) such that \(1\le a\le N\) and \(1\le b\le\) (current number of nodes in the large tree).
   2. Copy the subtree of the template tree rooted at node \(a\) and attach this copy as a new subtree of node \(b\) in the large tree.
   3. Renumber the newly added nodes with consecutive numbers in the same order as their original numbering in the template tree. For example, if before an operation the large tree had \(L\) nodes and the copied subtree contains \(C\) nodes, then the new nodes will be numbered \(L+1, L+2, \dots, L+C\) in an order that preserves the order of the corresponding nodes in the template tree.

After the building process, you are given \(Q\) queries. Each query asks for the distance (the number of edges on the unique path) between two nodes in the final tree.

Note: All formulas are shown in LaTeX format.

inputFormat

The input starts with three integers \(N\), \(M\) and \(Q\) separated by spaces.

Then follow \(N-1\) lines, each containing two integers \(u\) and \(v\), describing an edge of the template tree. It is guaranteed that the template tree is rooted at node \(1\).

Next, there are \(M\) lines. Each of these lines contains two integers \(a\) and \(b\) representing one operation.

Finally, there are \(Q\) lines, each containing two integers \(u\) and \(v\) representing a query asking for the distance between node \(u\) and node \(v\) in the final large tree.

outputFormat

For each query, output a single line containing one integer — the distance (the number of edges) between the two specified nodes.

sample

4 1 2
1 2
1 3
3 4
4 3
4 5
2 5

2
3