Đường cao tốc siêu không gian
Đề bài
Mô tả
Cho một đồ thị vô hướng đơn liên thông gồm đỉnh và cạnh, thoả mãn tính chất đặc biệt sau: với mọi chu trình đơn (đi qua mỗi đỉnh không quá một lần rồi quay về điểm xuất phát), tập hợp các đỉnh trên chu trình tạo thành một đồ thị con đầy đủ (mọi cặp đỉnh trên chu trình đều có cạnh nối trực tiếp).
Có truy vấn. Mỗi truy vấn cho hai đỉnh và ; hãy tính số cạnh ít nhất phải đi qua để di chuyển từ đỉnh đến đỉnh .
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên , , .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và () mô tả một cạnh nối hai đỉnh và .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và () mô tả một truy vấn.
Dữ liệu ra
In ra dòng, dòng thứ là số cạnh ít nhất cần đi qua để di chuyển từ đỉnh đến đỉnh .
Ràng buộc
- Đồ thị liên thông, đơn (không có cạnh bội, không có khuyên).
- Mọi chu trình đơn trong đồ thị đều tạo thành đồ thị con đầy đủ.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 7 2 1 2 1 3 1 4 2 3 2 4 3 4 1 5 1 4 2 5 |
1 2 |
Bốn đỉnh tạo thành một đồ thị đầy đủ , đỉnh chỉ nối với đỉnh . Từ đến có cạnh trực tiếp nên đáp án là . Từ đến phải đi qua đỉnh , mất cạnh. |
| 8 11 4 1 2 2 3 3 4 4 5 1 3 1 6 3 5 3 7 4 7 5 7 6 8 1 5 2 4 6 7 3 8 |
2 2 3 3 |
Các khối đầy đủ trong đồ thị là , , , . Đường đi ngắn nhất từ đến đi qua (2 cạnh); từ đến đi qua và (3 cạnh). |
Bình luận