Tuyến tránh nút bảo trì

Bối cảnh và bài toán

Một mạng giao thông có một số nút tạm thời bị khóa để bảo trì. Phương tiện không được đi qua các nút khóa, trừ khi đó không phải nguồn hay đích.

Yêu cầu

Tìm số cạnh ít nhất từ s tới t khi bỏ qua mọi nút bị khóa.

Input

Dòng đầu n, m, s, t, k. Dòng tiếp theo có k chỉ số nút bị khóa. Sau đó là m cạnh vô hướng.

Output

In khoảng cách ngắn nhất hoặc -1.

Ràng buộc

• 2 <= n <= 2*10^5
• 0 <= m <= 2*10^5
• 0 <= k <= n-2 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

6 6 1 6 1
3
1 2
2 3
2 4
4 5
5 6
3 6

Output

4

Giải thích. Các nút khóa bị xem như không tồn tại; BFS chạy trên phần mạng còn lại.

Ví dụ 2

Input

4 2 1 4 1
2
1 2
2 4

Output

-1

Giải thích. Các nút khóa bị xem như không tồn tại; BFS chạy trên phần mạng còn lại.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.