Thời điểm kết nối sớm nhất
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề 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$
Community Discussion