City Development

The city of Baytsburg has a historical part and a new part. The historical part is a tree of $n$ squares connected by $n-1$ avenues. The squares are numbered consecutively from 1 to $n$. The main square of the city, vertex 1, is the root of the tree.

At the start, the city consists only of the historical part. Each year the city develops as follows. Let $m$ be the number of squares at the start of the year.

• Choose a square $f$ in the historical part and a square $t$ among those already built (in the historical part or in the new part).
• The subtree $T$ of the historical part rooted at $f$ is copied entirely into the new part, then the root of the copied subtree is connected by an avenue to square $t$. All built objects (squares and avenues) belong to the new part. The historical part stays unchanged.
• Let $T$ consist of $k$ squares. The new squares get numbers from $m+1$ to $m+k$. If square $i$ has a smaller number than square $j$ in $T$, then the square $i'$ corresponding to $i$ has a smaller number than the square $j'$ corresponding to $j$.

You are given the configuration of the historical part and the development data for $y$ years. Answer queries that ask for the shortest distance between two squares.

The first line contains three integers $n$, $y$ and $q$: the number of squares in the historical part, the number of years the new part was built, and the number of queries ($1 \le n,y,q \le 10^5$).

Each of the next $n-1$ lines contains two integers $a$ and $b$, the numbers of two squares in the historical part connected by an avenue ($1 \le a,b \le n$; $a \ne b$). It is guaranteed that the squares and avenues form a tree. The main square, the root of the tree, has number 1.

Each of the next $y$ lines contains two integers $f$ and $t$: the number of the source square in the historical part and the number of the square to which the copy is attached ($1 \le f \le n$; $t \ge 1$, and $t$ does not exceed the number of squares at the start of the corresponding year).

Each of the next $q$ lines contains two integers $i$ and $j$, the numbers of the squares whose distance must be found. Let $M$ be the total number of squares after $y$ years of construction. Then $1 \le i,j \le M$.

For each query, print one integer: the shortest distance between the corresponding squares.