The Amestris government has been alerted of ~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~. 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.'s plan, and has decided to shut down all bidirectional roads between its
Note: We define a strangely connected component as a connected component that will not be disconnected by removing any 1 edge.
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~-th day.
Next ~Q~ lines: ~2~ integers ~x_i~ and ~y_i~, representing a query.
For full points, ~N, D, Q \le 150\,000~
For 5/25 points, ~N, D, Q \le 5\,000~
4 5 3 3 3 1 3 3 0 3 2 2 3 0 2 3 3 0 3
-1 0 -1