13081308 SUSTech Online Judge
Problem 1308 --Problem 5

1308: Problem 5

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 19  Solved: 3
[Submit][Status][Web Board]

Description

给一张\(n\)个点\(m\)条边的无向无权图,求从起点\(S\)到终点\(T\)的最短路径长度。

Input

第一行包含一个整数\(T(1\leq T\leq 10)\),表示样例个数。

对于每个样例,第一行包含四个整数\(n\),\(m\),\(S\)和\(T(2\leq n\leq 10^3,1\leq m\leq n*(n-1),1\leq S,T\leq n)\),含义如上所示。对于接下来的\(m\)行,每行包含两个整数\(u\)和\(v\),表示点\(u\)和点\(v\)之间有一条边。

Output

输出最短路径长度。如果无法到达则输出-1.

Sample Input

1
4 3 1 4
1 2
2 3
3 4

Sample Output

3

HINT

Source

 

[Submit][Status]