Một đất nước có \(n\) thành phố được đánh số từ 1 đến \(n\) và \(m\) con đường hai chiều nối trực tiếp giữa hai thành phố. Cho hai thành phố \(s,t\).

Yêu cầu: Tìm đường đi ngắn nhất từ thành phố \(s\) đến thành phố \(t\).

Input

• Dòng đầu chứa 4 số nguyên \(n,m,s,t (1≤s,t≤n≤1000;m≤2000).\)

• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) thể hiện con đường hai chiều nối trực tiếp giữa hai thành phố \(u,v\).

Output

• Ghi đường đi ngắn nhất từ \(s\) đến \(t\). Nếu không só đường đi từ \(s\) đến \(t\) ghi -1.

Sample Input

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

Sample Output

2