Dekaranger: 10 years after
Nhân chứng của vụ án đó - Carrie - đã xuất hiện tại trụ sở Dekaranger. Hiện đã được hạ ngầm xuống để tránh tình trạng bị xâm nhập như 10 năm về trước.
Sau khi tập hợp lực lượng để hộ tống Carrie đến trụ sở Tòa Án Tối Cao Vũ Trụ (cùng với Văn Phòng Khởi Tố Vũ Trụ) đặt tại hành tinh Gowashichoru, cả đội với chỉ huy lần này là DekaBlue Houji Tomasu đã ngay lập tức lên tàu vũ trụ để hộ tống nhân chứng.
Dù cho tàu có sử dụng các công nghệ hiện đại để tăng tốc, tuy nhiên, do hiện tượng Sion Morse ở khoảng cách 130,00km quanh hành tinh Gowashichoru, thời gian thực tế cảm nhận lại lâu hơn nhiều. Dòng chảy thời gian quanh hành tinh này được gọi là hiện tượng Sion Morse, thời gian chậm gấp 20 triệu lần. Tức là khi lệnh xin phán quyết được đưa ra, thời gian thực chờ đợi 10 giây, sẽ tương ứng 8 tháng tại hành tinh này.
Đúng lúc khi còn khoảng 4 giờ 20 phút (theo giờ Vũ Trụ), tàu hộ tống đã bị tấn công. Họ phải hạ cánh xuống hành tinh Riiyo - nơi mà kẻ địch đã phục kích từ trước. Trong khi cả đội đang chiến đấu, Houji và Sen đã nhanh chóng nhảy lên tàu vũ trụ và chạy thoát.
Lúc này, sau khi bị tấn công, hệ thống lái tự động đã gặp vấn đề. Houji phải lái thủ công. Tuy nhiên, do cậu đã dành 2 năm trong phòng máy tính để nghiên cứu về vụ án năm đó, cậu đã không còn thành thạo trong việc lái tàu vũ trụ. Biết rằng, SPD khắp vũ trụ chia thành $N$ phân khu, có $M$ liên kết giữa các phân khu này, và tất cả chúng đều là một chiều. Liên kết thứ $i$ giúp tàu vũ trụ của tổ chức di chuyển từ khu vực được phân khu $u_i$ phụ trách đến khu vực được phân khu $v_i$ phụ trách. Để đảm bảo an toàn, tàu vũ trụ vận hàng bằng việc di chuyển 3 bước. Cụ thể, để di chuyển từ khu vực $a$ đến khu vực $b$. Họ phải tìm thêm 2 khu vực $a_1$ và $a_2$ sao cho có thể di chuyển từ $a \rightarrow a1 \rightarrow a2 \rightarrow b$.
Hãy giúp Houji biết, đường đi ngắn nhất từ hành tinh Riiyo (tại khu vực $s$) đến trụ sở Tòa Án Tối Cao Vũ Trụ (tại khu vực $t$) là bao nhiêu?
Đôi chút về vụ án đó, 10 năm sau khi đánh bại Agent Abrella, các thành viên Dekaranger đã rẽ sang những con đường riêng (thực ra chỉ có Jasmine lấy chồng và Banban Akaza thực hiện nhiệm vụ của Fire Squad).
Tuy nhiên, một biến cố lớn xảy ra, đó là Doggie Kruger, chỉ huy của phân khu Trái Đất, bị buộc tội bán thông tin cơ mật cho Mafia Vũ trụ và bị bắn trọng thương. Ông cũng bị buộc tội sát hại 3 tên trong băng nhóm đó sau khi giao dịch và 1 người dân vô tội.
Mọi chi tiết thêm, vui lòng xem phim để tránh bị spoil.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N, M \ (1\le 2N, M \le 2\times 10^5)$;
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i, v_i \ (1\le u_i, v_i \le N)$;
- Dòng tiếp theo chứa hai số nguyên $s,t \ (1\le s,t \le N)$.
Dữ liệu đảm bảo không có hai cạnh nào trùng nhau.
Kết quả
- Kết quả bài toán. Nếu không có đáp án, ghi $-1$.
Ví dụ
Ví dụ 1
input
4 4
1 2
2 3
3 4
4 1
1 3
output
2
Ví dụ 2
input
3 3
1 2
2 3
3 1
1 2
output
-1
Ví dụ 3
input
2 0
1 2
output
-1
Comments