Thời điểm kết nối sớm nhất

Buổi 25 — Disjoint Set Union Data-structures Graphs
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho $N$ đỉnh đánh số từ $1$ đến $N$. Có $M$ cạnh được thêm vào tại các thời điểm $1, 2, \dots, M$ (mỗi thời điểm thêm 1 cạnh). Cho $Q$ truy vấn, mỗi truy vấn gồm hai đỉnh $u, v$ ($u \ne v$): hãy tìm thời điểm sớm nhất mà $u$ và $v$ trở nên liên thông với nhau. Nếu sau $M$ cạnh vẫn không liên thông, in ra -1.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, M, Q$ ($2 \le N \le 10^5, 0 \le M \le 2 \cdot 10^5, 1 \le Q \le 10^5$).
  • $M$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i, b_i$ mô tả cạnh thêm vào tại thời điểm $i$.
  • $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($u \ne v$).
Dữ liệu ra
  • Gồm $Q$ dòng, mỗi dòng là thời điểm sớm nhất hoặc -1.
Ví dụ
Input Output
4 3 3
1 2
3 4
2 3
1 2
1 3
2 4
1
3
3
Giới hạn
  • $2 \le N \le 10^5, 0 \le M \le 2 \cdot 10^5, 1 \le Q \le 10^5$
Draft saved