← 返回题目列表

Codeforces · 2113/E

E. 来自喀山的爱

中文机器翻译题面 查看原题

Marat 是喀山人。 Kazan 可以表示为由 $$$n$$$ 个顶点组成的无向树。马拉特年轻时经常陷入街头斗殴,现在他有$$$m$$$个敌人,数量从$$$1$$$到$$$m$$$,和他一起住在喀山。

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

所有敌人都通过最短路径去上班,并在$$$1$$$时间离开家。也就是说,如果我们将顶点 $$$a_i$$$ 和 $$$b_i$$$ 之间的最短路径表示为 $$$c_1, c_2, c_3, \ldots, c_k$$$ (其中 $$$c_1 = a_i$$$ 和 $$$c_k = b_i$$$),那么此时 $$$p$$$ ($$$1 \le p \le k$$$),编号为$$$i$$$的敌人将位于顶点$$$c_p$$$。

马拉确实不想在同一时间在同一顶点遇到任何敌人,因为这会造成尴尬的局面,但他们 可以在边缘相遇。 Marat 也会在 $$$1$$$ 时间离开他的家,并且在随后的每个时刻,他可以移动到相邻的顶点或停留在当前的顶点。

请注意,Marat 只能在 $$$2, 3, \ldots, k$$$ 时刻遇到第 $$$i$$$ 个敌人(其中 $$$c_1, c_2, \ldots, c_k$$$ 是顶点 $$$a_i$$$ 和 $$$b_i$$$ 之间的最短路径)。换句话说,从敌人上班的那一刻起,马拉 再也见不到他了.

帮助马拉找到他可以在途中不遇到任何敌人的情况下到达工作地点的最早时刻,或者确定这是不可能的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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 \neq y$$$) - 分别是树中的顶点数、敌人的数量以及 Marat 开始旅程和需要到达的顶点数。

以下 $$$n - 1$$$ 行中的第 $$$j$$$ 行包含两个整数 $$$v_j$$$ 和 $$$u_j$$$ ($$$1 \le v_j, u_j \le n$$$, $$$v_j \neq u_j$$$) — 树的第 $$$j$$$ 边的端点。

以下 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$, $$$a_i \ne x$$$) — Marat's 路线的描述敌人。

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

输出

对于每个测试用例,输出一个整数 - Marat 能够工作的最短时间,如果不可能,则输出 $$$-1$$$。

示例

输入
复制

5
4 1 1 4
1 2
2 3
3 4
4 1
5 1 1 5
1 2
2 3
3 4
4 5
5 1
9 2 1 9
1 2
2 3
3 4
3 5
5 6
6 7
6 8
8 9
9 1
7 1
9 2 7 2
1 4
2 5
3 6
4 5
5 6
4 7
5 8
6 9
2 8
3 7
3 2 1 3
1 2
2 3
2 1
3 1

输出
复制

4
6
10
5
-1

注意

在第一个测试用例中,可以通过最短路径从顶点号 $$$1$$$ 到达顶点号 $$$4$$$。请注意,马拉将在边缘而不是顶点遇到单个敌人。

在第二个测试用例中,最优策略是在起始顶点等待一时刻,然后沿着从顶点 $$$1$$$ 到顶点 $$$5$$$ 的最短路径。如果马拉不从一开始就停下来,他就会在顶点而不是边缘与敌人相遇。

在第三个测试用例中,从顶点 $$$1$$$ 到顶点 $$$4$$$ 是有益的。之后,他在某一时刻不应向任何地方移动,然后沿着从顶点$$$4$$$到顶点$$$9$$$的最短路径走。