Sau một số rủi ro và thất bại trong kinh doanh, tổng giám đốc công ty A quyết định tổ chức cho các giám đốc 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 A 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 hai giám đốc 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 giám đốc 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 giám đốc 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 một chiều.
• Các giám đốc khi đi trong mạng thì mỗi giờ đi được theo đúng một tuyến đường và phải liên tục di chuyển cho đến khi hai giám đốc gặp nhau tại một đại lý nào đó thì dừng lại (các giám đốc không được dừng lại để chờ giám đốc kia đến).
• Các giám đốc khi đi phải xuất phát cùng lúc.

Tuy mạng hơi tệ nhưng là mạng nội bộ nên không có chuyện tắc đường. Vì vậy, trong một giờ luôn có thể di chuyển từ đại lý này sang đại lý khác nếu có đường. Tổng giám đốc 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à hai giám đốc ở hai đại lý cho trước có thể gặp nhau. Đáng tiếc là tổng giám đốc chỉ giỏi kinh doanh, còn lập trình thì quá yếu kém.

Yêu cầu:

Bạn hãy viết chương trình giúp tổng giám đốc sắp xếp lịch đi của hai giám đốc sao cho thời gian ít nhất.

Dữ liệu vào

• Dòng đầu ghi hai số ~N, M~ là số đại lý và số tuyến đường trong mạng giao thông của công ty A. (~0<M,N \leq 250~)</li>
• Dòng thứ hai ghi ~S,T~ lần lượt là số thứ tự hai đại lý có hai giám đốc cần phải gặp nhau ~(0<S,T \leq N)~.</li>
• ~M~ dòng tiếp theo mỗi dòng ghi hai số nguyên ~U, V~ thể hiện có đường đi một chiều từ ~U~ tới ~V~ ~(0 < U,V \leq N)~.
  Các số trên một dòng viết cách nhau ít nhất một dấu cách.

Kết quả ra

Một dòng duy nhất chứa thời gian nhỏ nhất hai giám đốc có thể gặp nhau.

Sample Input

6 7
1 5
1 2
4 5
2 3
3 4
4 1
5 4
5 6

Sample Output

3