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 "~x\ y~", 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 150\,000~.
For 5/25 points, ~N, D, Q \le 5\,000~.

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