题目描述

给定一个 $n$ 个点，$m$ 条边的 无向图，节点依次用 $0 \sim (n-1)$ 的整数编号。

初始时，你位于节点 $s$，你想要前往点 $t$，默认节点 $s$ 已经访问过。

你每次可以执行以下两个操作之一：

• 设当前你在节点 $u$，选择一条边 $(u,v)$，移动到节点 $v$；
• 令 $S$ 是当前已被访问的点的编号组成的集合，令 $x = \operatorname{mex}(S)$，移动到节点 $x$。

一个集合的 $\operatorname{mex}$ 值是其中最小的未出现的非负整数。

• 例如 $\operatorname{mex}(0,1,2)=3$，$\operatorname{mex}(1,2,4)=0$。

你需要求出到达节点 $t$ 最小需要的操作次数。

输入格式

本题有多组测试数据。

第一行，包含一个正整数 $T$，表示测试组数。对于每组测试数据：

• 第一行，四个整数 $n,m,s,t$。
• 接下来 $m$ 行，每行两个整数 $u,v$，表示图中的一条边 $(u,v)$。

输出格式

共 $T$ 行，每组测试数据输出一行。

2
20 20 15 8
2 2
5 6
7 16
12 6
2 9
8 17
16 16
5 15
12 10
14 6
14 1
0 16
14 7
17 5
6 19
2 19
19 12
9 8
0 0
15 15
5 1 0 4
0 1

3
4

提示

数据范围

令 $N=\sum\limits n,M=\sum\limits m$。

对于全部的数据：$1 \le N,M \le 2\times 10^5$，$1 \le n,m \le 2\times 10^5$，$0 \le s,t,u,v \lt n$。

可能有重边，自环，图不保证连通，详细数据范围见下表。