Số máy trung chuyển ít nhất

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

Một thông điệp được gửi từ máy 1 đến máy n qua các kết nối hai chiều. Mỗi máy trên tuyến, kể cả nguồn và đích, đều được tính.

Yêu cầu

Tìm số máy ít nhất xuất hiện trên một tuyến hợp lệ từ 1 tới n; nếu không có tuyến, in -1.

Input

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

Output

In số máy ít nhất hoặc -1.

Ràng buộc

• 2 <= n <= 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–04 | | S2 | 60 | Không có ràng buộc bổ sung | 05–10 |

Ví dụ 1

Input

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

Output

3

Giải thích. BFS cho số cạnh ngắn nhất; số máy trên tuyến bằng số cạnh cộng 1.

Ví dụ 2

Input

3 1
1 2

Output

-1

Giải thích. BFS cho số cạnh ngắn nhất; số máy trên tuyến bằng số cạnh cộng 1.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Message Route. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.