城市交通

题目内容

题目描述

某国共有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的路径中最少需要经过几条道路。

样例输入

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

样例输出

2

提示

提交评测
请登录后再操作

题目描述

城市交通
1116
0
Level2
55
36
65%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在