Hệ Thống Kết Nối Tối Ưu

Buổi 43 — SCC (Tarjan) & 2-SAT
Points
60
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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
Draft saved