QBAGENTS - Các đại lý
Giới hạn- Thời gian: 0.039s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Sau một số rủi ro và thất bại trong kinh doanh, tổng giám đốc công ty Fsoft là Zone quyết định tổ chức cho các sếp nhỏ của các đại lý thuộc công ty gặp mặt và thảo luận với nhau. Công ty Fsoft là một công ty cực kì lớn trải khắp toàn cầu nên một vấn đề lớn đặt ra là làm sao tổ chức cho 2 sếp nhỏ gặp nhau trong thời gian sớm nhất. Vấn đề đặc biệt trở nên hóc búa vì các nhân viên của công ty chỉ được đi bằng mạng giao thông của công ty để đảm bảo an toàn, bảo mật và chi phí. Nhưng mạng này lại hơi tệ:
- Các nhân viên buộc phải di chuyển theo các tuyến giao thông giữa các đại lý.
- Mạng giao thông của công ty là mạng gồm các tuyến đường 1 chiều.
- Các nhân viên khi đi trong mạng thì mỗi giờ đi được theo đúng 1 tuyến đường và phải liên tục di chuyển (nghĩa là không được dừng lại).
Được cái đây là mạng nội bộ và với công nghệ đỉnh cao nên không có chuyện tắc đường. Vì vậy, trong 1 giờ luôn có thể di chuyển từ đại lý này sang đại lý khác nếu có đường.
Zone muốn nhân viên của mình không lãng phí thời gian. Bởi vậy ông muốn tính thời gian ngắn nhất mà 2 sếp ở 2 đại lý cho trước có thể gặp nhau. Đáng tiếc là Zone chỉ giỏi kinh doanh, còn lập trình thì quá yếu kém. Bạn là nhân viên dưới quyền Zone và đang rất muốn thể hiện khả năng của mình. Vậy thì, hãy nhân cơ hội này để cho Zone thấy trình độ tuyệt vời của bạn.
Input
Dòng đầu ghi 2 số N, M là số đại lý và số tuyến đường trong mạng giao thông của công ty Fsoft. (N ≤ 250)
Dòng thứ 2 ghi S,T lần lượt là số thứ tự 2 đại lý có 2 sếp cần phải gặp nhau.
M dòng tiếp theo mỗi dòng ghi 2 số nguyên U, V thể hiện có đường đi một chiều từ U tới V.
Output
Gồm một dòng duy nhất ghi thời gian nhỏ nhất 2 sếp có thể gặp nhau.
Nếu 2 sếp không thể gặp nhau ghi -1.
Example
Input: 6 7 1 5 1 2 4 5 2 3 3 4 4 1 5 4 5 6 Output: 3
- Người up: cun