Escape The Maze (hard version)
Contest: Codeforces Round 756 (Div. 3)
Difficulty rating: 1900
Tags: dfs and similar, dp, greedy, shortest paths, trees

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.

Input format:
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 < 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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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".

Example input:
4

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

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

3 1
2
1 2
2 3

3 2
2 3
3 1
1 2

Example output:
-1
2
1
2

Editorial:
Let's learn how to find an answer for the subtree rooted in vertex $$$v$$$. At first, it is obvious from E1 tutorial that if the nearest to $$$v$$$ vertex with a friend from this subtree is no further from it than the root of the entire tree from $$$v$$$, then the answer for the entire subtree is $$$1$$$ since a friend can come to $$$v$$$ and catch Vlad in it not allowing him to go to any leaf of this subtree. Else we will find the answer leaning on its children. If a solution does not exist for at least one child, then it does not exist for the entire subtree, because after reaching $$$v$$$ Vlad will be able to go to such child and reach any exit. Otherwise, the answer for $$$v$$$ is the sum of the answers of its children, since we need to beat it in each subtree to win, and for each subtree, we have found the minimum answer.