When Did We Meet

Difficulty: 1850 6000 ms 128 MB

binary-search union-find offline

Edges arrive at times 1..M. For each query (u, v), print the earliest time at which u and v become connected (0 if u = v, −1 if never).

Input: the first line has N, M and Q; the next M lines have the edges in time order; the next Q lines have the queries.

Output: one line per query.

Constraints:

• 2 ≤ N ≤ 10⁵
• 1 ≤ M, Q ≤ 10⁵

Sample Tests

4 3 2
1 2
3 4
2 3
1 4
1 3

3
3

2 1 1
1 2
2 2

0

Read the Editorial