## Mock CCO '17 Day 1 P3 - Connection

View as PDF

Points: 30 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem types

The Amestris government has been alerted of imaxblue’s plan, and has decided to shut down all bidirectional roads between its cities, numbered to . However, they are going to be slowly reopening roads, at a steady rate of road per day, for days to . 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 queries in the form "", asking the first day on which and will be strangely connected, or 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:
Next lines: integers and , representing that cities and are connected on the -th day.
Next lines: integers and , representing a query.

For full points,
For 5/25 points,

#### 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