题目描述

Steve和Amy一同坐飞机去旅游。他们现在位于 1 号城市，目标是 5 号城市，可是 1 号城市并没有到 5 号城市的直航。不过Steve已经收集了很多航班的信息，现在Steve希望找到一种乘坐方式，使得转机的次数最少，如何解决呢？

输入格式

第一行输入城市的数量n（顶点），航线的数量m（边），出发城市，目的城市。
后面若干行表示航班的线路。

输出格式

一行，从出发城市到目的城市最少的转机次数，如果无法到达，输出-1。

样例数据

input

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

output

1

数据范围

1<n<=1000
1<m<=300000