文理学院程序设计在线练习


栗酱快跑

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 33   Accepted Submission(s): 10
Problem Description

栗酱现在面临一个非常大的问题,她要非常快的逃离这片区域,请给定一个最快可行的方案。
这片区域可以等价于一个有n个点,m条有向边的图,每条边的路径大小为1。
栗酱起点为1,希望到达终点为n,请给出她能逃到终点的最短路径长度p。

Input

第一行数据组数T(T<=7)。
对于每组数据第一行,整数n,m(2<=n<=1000,m<=1000)。
接下来m行,给出三个用空格分开的整数u,v,表示从u到v有一条有向边。

Output

每组数据输出一行,一个正整数p。若没有到达终点的路径,输出-1。

Sample Input
2
3 2
1 2
2 3
3 1
1 2
Sample Output
2
-1
Source

第12届校赛