题目描述
给出一个有向图,并给出两点s和t,求从s出发,最少经过几条边可以到达t
图中可能存在重边(即连接同一对顶点的两条及以上的边)和自环(即连接某个点和它自身的边)
输入描述
输入的第一行为2个正整数n,m。分别表示给出的图的顶点数和边数。(1 <= n <= 200, 1 <= m <= n*(n-1)/2 )
接下来m行,每行两个正整数x,y。表示图中存在一条由x指向y的边。(顶点编号从1到n)
输出描述
输出一行,包含一个整数,为题目所求的边数,如果s不能到达t,则输出-1
样例输入
5
5
1 2
2 3
3 5
1 4
4 5
1 5
样例输出
2
提示