Hạo và Huy đang lạc nhau ở Rừng tre Lạc lối. Khu rừng có thể được biểu diễn bằng một đồ thị vô hướng \(n\) đỉnh và \(m\) cạnh. Hạo hiện đang ở đỉnh \(a\) còn Huy hiện đang ở đỉnh \(b\). Cứ mỗi \(1\) đơn vị thời gian, Hạo và Huy có thể di chuyển sang một đỉnh kề bất kì (cả hai sẽ không đứng yên vì hiện đang rất vội). Xác định thời điểm sớm nhất cả hai có thể gặp lại nhau.

Input

• Dòng đầu tiên gồm \(2\) số nguyên \(n,m\).
• Dòng thứ hai gồm \(2\) số nguyên \(a,b\).
• \(m\) dòng tiếp theo, mỗi dùng gồm \(2\) số nguyên \(u,v\), thể hiện có cạnh nối \(u\) và \(v\).

Output

• In ra thời điểm sớm nhất họ có thể gặp lại nhau. Hoặc in ra -1 nếu cả hai lạc nhau mãi mãi…

Điều kiện

• \(1 \le n,m \le 10^3\)
• \(1 \le u,v,a,b \le n\)

Sample Input 1

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

Sample Output 1

2