Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBAGENTS - Các đại lý

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

Được gửi lên bởi:special_one
Ngày:2008-10-12
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2017-11-02 02:57:25
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/1368/qbagents-spoj/
2014-08-31 05:58:30 Hướng Thái Dương
M<n*(n-1)?
2014-08-31 05:58:30 Hướng Thái Dương
M<n*(n-1)?
2012-11-15 09:07:56 Ðẹp trai có gì sai
Trường hợp nào thì không thể gặp nhau???
2012-09-14 13:06:49 Nguyễn Tất Thắng
thằng 1 đi 1 -> 2 -> 3 -> 4
thằng 2 đi 5 -> 4 -> 5 -> 4
2012-05-23 17:22:33 hiepsieunhan
Gioi han cua m la ji vay ??!
2011-03-23 04:13:54 T-7
2 sếp nhỏ sẽ gặp nhau tại vị trí 4
Sếp ở vị trí 1->2->3->4: 3 giờ
Sếp ở vị trí 5->4->5->4: 3 giờ (do ko đc dừng lại nên phải đi vòng vòng)

Last edit: 2011-03-23 04:27:55
2010-12-03 08:22:33 bad coder !
Đường đi ngắn nhất là 4: 1-->2-->3-->4-->5
Sao lại ra 3 được nhỉ ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.