题目描述

小 A 和小 B 在玩一个博弈游戏。

这个博弈游戏在一张 $n$ 个点、$m$ 条边的图上进行，小 A 最开始有一个棋子在 $S$ 号节点上，小 B 最开始有一个棋子在 $T$ 号节点上。

小 A 需要将棋子移动到 $T$ 号节点，小 B 需要将棋子移动到 $S$ 号节点，任意时刻不能存在一个节点同时包含两枚棋子。并且游戏总是小 A 先手，小 B 后手，每次执行操作的人可以选择不移动。

每个人都要尽可能先完成自己的目标，他们可以通过无向图点与边之间的关系制定防守和攻击策略以扰乱对方的节奏从而获得胜利。

两人玩得酣畅淋漓，长期地使用一个规则未免让人感到疲倦，于是他们决定，去掉防守和反击策略，即两个人只需要把各自的棋子移动到对应目标节点即可。

小 A 想问你，当他们都执行最优策略的时候，两枚棋子的移动步数总和至少多少步？

输入格式

第一行两个整数 $C,T$，表示测试点编号和数据组数，在样例中 $C=0$。

接下来 $T$ 组数据，每组数据第一行四个整数 $n,m,S,T$，含义如题所示。

接下来 $m$ 行，每行两个整数 $x,y$，表示无向图上存在一条连接 $x,y$ 的无向边。

输出格式

对于每组数据输出答案，如果无解，输出 -1。

样例 1

输入

0 3
4 3 4 3
2 4
1 4
3 4
2 3
2 1 1 2
1 2
5 6 3 5
1 2
2 3
1 5
2 4
1 3
2 5

输出

3
-1
4

样例 1 解释

对于第一组数据，可以将 3 号位置上的棋子移动到 2 号位置，然后将 4 号位置上的棋子移动到 3 号位置，最后将 2 号位置上的棋子移动到 4 号位置即可达成目标。

数据范围

对于 100% 的数据，满足 $1\le T\le 5$，$1\le n,m\le 2\times 10^5$，$1\le x,y\le n$，保证图无重边、自环。

• 特殊性质 A：保证图无环。
• 特殊性质 B：保证答案小于等于 3。
• 特殊性质 C：保证 $n=m$ 且图连通。