Cho một đồ thị có hướng \(G\) gồm \(n\) đỉnh và \(m\) cung, hai con Rô-bốt đứng tại hai đỉnh nào đó.

Yêu cầu: Chuyển nhanh nhất hai con Rô-bốt đến gặp nhau tại một đỉnh của đồ thị, biết rằng cả hai con Rô-bốt chỉ được chạy theo các cung định hướng và không được dừng lại cho tới lúc gặp nhau tại một đỉnh nào đó. Thời gian Rô-bốt đi qua một cung bất kỳ luôn là 1 đơn vị thời gian.

Input

• Dòng 1: chứa 4 số nguyên dương \(n,m,A,B\). Ở đây \(A\) và \(B\) lần lượt là vị trí của con rô-bốt thứ nhất và vị trí của con rô-bốt thứ hai, \((2≤n≤250; 1≤m≤60000).\)

• \(m\) dòng tiếp theo, mỗi dòng chứa hai số \(u,v\) tương ứng với một cung \((u,v)\) của đồ thị \(G\).

Output

• Ghi thời gian tính từ lúc bắt đầu di chuyển cho tới lúc hai rô-bốt gặp nhau.

Sample Input

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

Sample Output

3