Hệ Thống Kết Nối Tối Ưu
Points
60
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Đề bài
Cho N thành phần mạng và M kết nối một chiều. Có Q truy vấn, mỗi truy vấn cho hai số u và v. Với mỗi truy vấn, hãy tìm số đỉnh tối thiểu cần đi qua (bao gồm cả u và v) trên đường đi từ u đến v trong đồ thị rút gọn (condensation DAG). Nếu không thể đi từ u đến v, in -1.
Lưu ý: hai đỉnh cùng SCC có khoảng cách 0, đường đi trên condensation DAG đếm số SCC đi qua.
Dữ liệu vào
- Dòng đầu: ba số nguyên N, M, Q (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000, 1 ≤ Q ≤ 100000)
- M dòng tiếp theo: u v
- Q dòng tiếp theo: u v
Dữ liệu ra
- Q dòng, mỗi dòng một số nguyên.
Ví dụ
| Input | Output |
|---|---|
| 6 7 3\n1 2\n2 3\n3 1\n4 5\n5 6\n6 4\n3 4\n1 5\n5 1\n2 2 | 2\n-1\n1 |
Giới hạn
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ 200000
- 1 ≤ Q ≤ 100000
Community Discussion