某国共有N座城市,他们的编号分别是1,2,3……N,城市与城市之间通过道路相连,有些城市之间没有道路,那么它们可以通过先到其他城市,再到目的城市,一共有M条道路,且保证任意两个城市之间的道路不超过1条,小明一家到这个国家旅游,他想从城市S出发到城市T,求他最少需要经过几条道路才能到达目的地。
第一行有四个正整数N M S T,分别代表城市数,道路数,出发城市编号的终点城市编号
满足N<1000,M<50000且S,T<=N。
接下来M行,每行两个正整数X,Y,代表城市X和Y之间存在一条道路。
输出共一行,用一个正整数表示S到T的路径中最少需要经过几条道路。
请输入正确的证书编号
学员姓名:孙兴民
课程:Scratch Level 1
发证日期:2019.08.15