Mock CCO '17 Problem 3 - Connection

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.2s
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 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

Comments

There are no comments at the moment.