Mock CCO '17 Day 1 P3 - Connection

View as PDF

Submit solution

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 N cities, numbered 0 to N-1. 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-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

Comments


  • 0
    wleung_bvg  commented on Aug. 9, 2018, 8:09 p.m.

    There appears to be test cases where a == N or b == N, despite the cities being numbered from 0 to N - 1.


  • 0
    wleung_bvg  commented on March 28, 2018, 8:23 p.m. edited

    (deleted)