The Amestris government has been alerted of imaxblue's plan, and has decided to shut down all bidirectional roads between its $N+1$ cities, numbered $0$ to $N$. However, they are going to be slowly reopening roads, at a steady rate of $1$ road per day, for days $0$ to $D-1$. imaxblue knows their plan, and will only move between two cities if he knows that they are in the same strangely connected component. He will ask $Q$ queries in the form "$xy$", asking the first day on which $x$ and $y$ will be strangely connected, or $-1$ if it will never be strangely connected.

Note: We define a strangely connected component as a connected component that will not be disconnected by removing any 1 edge.

Input Specification

First line: $N,D,Q$
Next $D$ lines: $2$ integers $A_i$ and $B_i$, representing that cities $A_i$ and $B_i$ are connected on the $i^{\text{th}}$ day.
Next $Q$ lines: $2$ integers $x_i$ and $y_i$, representing a query.

Subtasks

For full points, $N,D,Q\le 150000$.
For 5/25 points, $N,D,Q\le 5000$.

Sample Input

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

Sample Output

-1
0
-1