CF1611E2.Escape The Maze (hard version)

The only difference with E1 is the question of the problem.

Vlad built a maze out of $n$ rooms and $n-1$ bidirectional corridors. From any room $u$ any other room $v$ can be reached through a sequence of corridors. Thus, the room system forms an undirected tree.

Vlad invited $k$ friends to play a game with them.

Vlad starts the game in the room $1$ and wins if he reaches a room other than $1$, into which exactly one corridor leads. Friends are placed in the maze: the friend with number $i$ is in the room $x_i$, and no two friends are in the same room (that is, $x_i \neq x_j$ for all $i \neq j$). Friends win if one of them meets Vlad in any room or corridor before he wins.

For one unit of time, each participant of the game can go through one corridor. All participants move at the same time. Participants may not move. Each room can fit all participants at the same time.

Friends know the plan of a maze and intend to win. They don't want to waste too much energy. They ask you to determine if they can win and if they can, what minimum number of friends must remain in the maze so that they can always catch Vlad.

In other words, you need to determine the size of the minimum (by the number of elements) subset of friends who can catch Vlad or say that such a subset does not exist.

与 E1 唯一的区别在于本题的问题描述。

弗拉德用 $n$ 个房间和 $n-1$ 条双向走廊建造了一个迷宫。从任意房间 $u$ 出发，均能通过一系列走廊到达任意其他房间 $v$。因此，房间系统构成一棵无向树。

弗拉德邀请了 $k$ 位朋友一起玩游戏。

游戏开始时，弗拉德位于房间 $1$；若他抵达某个非房间 $1$、且仅有一条走廊与之相连的房间，则他获胜。朋友们被安排在迷宫中：编号为 $i$ 的朋友位于房间 $x_i$，且任意两位朋友均不在同一房间（即对所有 $i \neq j$，均有 $x_i \neq x_j$）。若在弗拉德获胜前，有任意一位朋友在某个房间或某条走廊上与弗拉德相遇，则朋友们获胜。

每单位时间，游戏的每位参与者均可穿过一条走廊。所有参与者同时移动，但也可选择不动。每个房间可同时容纳所有参与者。

朋友们知晓迷宫的结构，并希望获胜。但他们不想耗费过多体力。因此，他们请你判断：他们能否获胜？若能获胜，至少需要保留多少位朋友在迷宫中，才能保证一定可以抓住弗拉德？

换言之，你需要求出能够抓住弗拉德的朋友子集的最小大小（即元素个数最少），或判定这样的子集不存在。

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. The input contains an empty string before each test case.

The first line of the test case contains two numbers $n$ and $k$ ($1 \le k \lt n \le 2\cdot 10^5$) — the number of rooms and friends, respectively.

The next line of the test case contains $k$ integers $x_1, x_2, \dots, x_k$ ($2 \le x_i \le n$) — numbers of rooms with friends. All $x_i$ are different.

The next $n-1$ lines contain descriptions of the corridors, two numbers per line $v_j$ and $u_j$ ($1 \le u_j, v_j \le n$) — numbers of rooms that connect the $j$ corridor. All corridors are bidirectional. From any room, you can go to any other by moving along the corridors.

It is guaranteed that the sum of the values $n$ over all test cases in the test is not greater than $2\cdot10^5$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示输入中测试用例的数量。每个测试用例前均有一行空字符串。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \lt n \le 2\cdot 10^5$）—— 分别表示房间数量和朋友数量。

测试用例的第二行包含 $k$ 个整数 $x_1, x_2, \dots, x_k$（$2 \le x_i \le n$）—— 表示有朋友的房间编号。所有 $x_i$ 互不相同。

接下来的 $n-1$ 行描述走廊，每行包含两个整数 $v_j$ 和 $u_j$（$1 \le u_j, v_j \le n$）—— 表示第 $j$ 条走廊所连接的两个房间编号。所有走廊均为双向通行。从任意一个房间出发，均可通过走廊到达其他任意房间。

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

Print $t$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be $-1$ if Vlad wins anyway and a minimal number of friends otherwise.

输出 $t$ 行，每行包含对应测试用例的答案。若弗拉德无论如何都会获胜，则该测试用例的答案为 $-1$；否则为所需的最少朋友数量。

In the first set of inputs, even if all the friends stay in the maze, Vlad can still win. Therefore, the answer is "-1".

In the second set of inputs it is enough to leave friends from rooms $6$ and $7$. Then Vlad will not be able to win. The answer is "2".

In the third and fourth sets of inputs Vlad cannot win only if all his friends stay in the maze. Therefore the answers are "1" and "2".

在第一组输入中，即使所有朋友都留在迷宫中，弗拉德仍然能够获胜。因此答案为“-1”。

在第二组输入中，只需让房间 $6$ 和 $7$ 中的朋友离开即可。此时弗拉德将无法获胜。答案为“2”。

在第三组和第四组输入中，仅当弗拉德的所有朋友都留在迷宫中时，弗拉德才无法获胜。因此答案分别为“1”和“2”。