安徽科技工程大学程序设计在线考试系统Ver3.0

诚信考试,杜绝作弊!

问题 L: 最小转机

内存限制:512 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

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

输入格式

多组输入。

第一行输入n , m , start , end , 其中n表示城市数,m表示航线数,start表示起点城市,end 表示终点城市。紧接着输入m行,每行是一条类似a b这样的数据表示城市a和城市b之间有航线,也就是说城市a和城市b之间可以互相到达。


输出格式

输出最少转机数,若不能到达请输出"Connot reach"。

输入样例 复制

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

输出样例 复制

2

数据范围与提示

起终点为0时不可达