Tìm đường đi có ít bước đi nhất từ đỉnh u đến đỉnh v trong đồ thị vô hướng.

Input

Dòng 1 là 4 số nguyên dương n, m, u, v tương ứng là số đỉnh và số cạnh của đồ thị (n ≤ 50, m ≤ 200) và 2 đỉnh đầu cuối.

m dòng tiếp theo, mỗi dòng ghi 2 số u v là 2 đỉnh của một cạnh của đồ thị.

Output

Ghi ra số bước đi từ u đến v.

Ví dụ: input

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

output

2