Số chặng truyền tối thiểu

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

Một gói dữ liệu cần được chuyển qua mạng liên kết hai chiều. Mỗi lần đi qua một liên kết được tính là một chặng.

Yêu cầu

Tìm số chặng ít nhất từ nút s tới nút t; nếu không thể tới, in -1.

Input

Dòng đầu n, m, s, t; tiếp theo m cạnh u, v.

Output

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

Ràng buộc

• 2 <= n <= 2*10^5
• 0 <= m <= 2*10^5 ## 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

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

Output

2

Giải thích. BFS mở rộng theo lớp số cạnh, nên khoảng cách đầu tiên tới đích là số chặng nhỏ nhất.

Ví dụ 2

Input

4 1 1 4
1 2

Output

-1

Giải thích. BFS mở rộng theo lớp số cạnh, nên khoảng cách đầu tiên tới đích là số chặng nhỏ nhất.

Gợi ý

Hãy bắt đầu bằng cách phân loại graph, mục tiêu truy vấn và constraints; sau đó đối chiếu với Decision Map của buổi học trước khi viết code.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.