给一张\(n\)个点\(m\)条边的无向无权图,求从起点\(S\)到终点\(T\)的最短路径长度。
给一张\(n\)个点\(m\)条边的无向无权图,求从起点\(S\)到终点\(T\)的最短路径长度。
第一行包含一个整数\(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\)之间有一条边。
输出最短路径长度。如果无法到达则输出-1.
1
4 3 1 4
1 2
2 3
3 4
3