CF2113E.From Kazan with Love

Marat 是喀山的本地人。喀山可以表示为一个包含 $n$ 个顶点的无向树。在他年轻的时候，Marat 经常卷入街头斗殴，现在他有 $m$ 个敌人，这些敌人和他一样都住在喀山，编号从 $1$ 到 $m$。

每天，城市里的所有人都要去上班。Marat 知道他的第 $i$ 个敌人住在顶点 $a_i$，工作在顶点 $b_i$。他自己住在顶点 $x$，工作在顶点 $y$。保证 $a_i \ne x$。

所有敌人都会沿着最短路径去上班，并且都在时刻 $1$ 离开家。也就是说，如果我们用 $c_1, c_2, c_3, \ldots, c_k$ 表示从顶点 $a_i$ 到 $b_i$ 的最短路径（其中 $c_1 = a_i$，$c_k = b_i$），那么在时刻 $p$（$1 \le p \le k$）时，第 $i$ 个敌人会在顶点 $c_p$。

Marat 非常不想在同一时刻与任何一个敌人在同一个顶点相遇，因为这会造成尴尬的局面，但他们可以在一条边上相遇。Marat 也会在时刻 $1$ 离开家，在之后的每一个时刻，他可以选择移动到相邻的顶点，或者留在当前位置。

注意，Marat 只能在时刻 $2, 3, \ldots, k$（其中 $c_1, c_2, \ldots, c_k$ 是从 $a_i$ 到 $b_i$ 的最短路径）与第 $i$ 个敌人相遇。换句话说，从敌人到达工作地点的时刻起，Marat 就无法再与他相遇。

请帮助 Marat 找到他能够不与任何敌人在路上相遇、最早到达工作的时刻，或者判断是否不可能做到。

每个测试点包含多组测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。每组测试用例的描述如下。

每组测试用例的第一行包含四个整数 $n$、$m$、$x$ 和 $y$（$2 \le n \le 10^5$，$1 \le m \le 200$，$1 \le x, y \le n$，$x \ne y$），分别表示树的顶点数、敌人数、Marat 的起点和终点。

接下来的 $n-1$ 行，每行包含两个整数 $v_j$ 和 $u_j$（$1 \le v_j, u_j \le n$，$v_j \ne u_j$），表示树中的一条边。

接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$，$a_i \ne x$），表示第 $i$ 个敌人的起点和终点。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试用例，输出一个整数，表示 Marat 最早能够到达工作的时刻，或者如果无法做到则输出 $-1$。

在第一个测试用例中，可以沿最短路径从顶点 $1$ 到达顶点 $4$。注意，Marat 会在一条边上与敌人相遇，而不是在顶点上。

在第二个测试用例中，最优策略是在起点等待一段时间，然后再沿最短路径从顶点 $1$ 到顶点 $5$。如果一开始不等待，Marat 会在顶点上与敌人相遇。

在第三个测试用例中，先从顶点 $1$ 到达顶点 $4$，然后在该处等待一段时间，再沿最短路径从顶点 $4$ 到顶点 $9$。

由 ChatGPT 4.1 翻译