Món quà
Đề bài
Mô tả
Tuấn tặng con trai một đồ thị có hướng không trọng số làm quà sinh nhật. Đồ thị có đỉnh, đánh số từ đến , và cạnh có hướng, đánh số từ đến .
Tuấn muốn kiểm tra IQ của con bằng một trò chơi. Trò chơi gồm lượt, ở mỗi lượt Tuấn yêu cầu con giải một trong hai loại câu hỏi sau:
- Xóa một cạnh khỏi đồ thị.
- Tìm độ dài đường đi ngắn nhất từ đỉnh đến một đỉnh .
Tuấn muốn con trả lời mỗi câu hỏi loại thứ hai ngay lập tức, không được biết trước bất kỳ câu hỏi nào phía sau.
Lưu ý:
- Một đường đi độ dài của đồ thị là một dãy đỉnh sao cho có cạnh từ đến với mọi .
- Một đường đi độ dài là đường đi ngắn nhất từ đến nếu không tồn tại đường đi nào khác từ đến có độ dài nhỏ hơn .
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và là số đỉnh và số cạnh của đồ thị (, ).
- Dòng thứ trong dòng tiếp theo chứa hai số nguyên và , nghĩa là có một cạnh có hướng từ đến .
- Dòng tiếp theo chứa một số nguyên là số câu hỏi ().
- dòng còn lại mô tả các câu hỏi, mỗi câu hỏi có một trong hai dạng sau:
- : xóa cạnh có chỉ số , trong đó là câu trả lời của câu hỏi loại gần nhất trước đó. Trước câu hỏi loại đầu tiên, . Nếu không có đường đi từ đến đỉnh được hỏi thì . Đảm bảo mỗi cạnh bị xóa nhiều nhất một lần.
- : hỏi độ dài đường đi ngắn nhất từ đỉnh đến đỉnh .
Dữ liệu ra
Với mỗi câu hỏi loại thứ hai, in câu trả lời trên một dòng. Nếu không có đường đi từ đến , in ra .
Ràng buộc
- , .
- .
- .
- Với câu hỏi loại : và ; mỗi cạnh bị xóa nhiều nhất một lần.
- Với câu hỏi loại : .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 6 1 4 1 3 4 2 1 2 2 3 3 4 7 1 1 2 3 1 1 2 3 2 2 1 0 2 3 |
2 3 2 -1 |
Các cạnh thực sự bị xóa lần lượt là cạnh , và . Ví dụ, câu hỏi thứ ba có , nên xóa cạnh . |
| 5 7 1 2 2 3 3 4 1 3 4 5 2 2 5 1 9 2 5 1 0 2 5 2 1 1 2 2 4 2 5 1 1 2 2 |
3 4 0 -1 -1 -1 |
Các cạnh bị xóa lần lượt là cạnh (), () và (). Câu hỏi xóa cuối cùng có nên xóa cạnh . |
Bình luận