Vlad and Unfinished Business solution codeforces

Vlad and Unfinished Business solution codeforces

 

Vlad and Nastya live in a city consisting of nn houses and n1n−1 road. From each house, you can get to the other by moving only along the roads. That is, the city is a tree.

Vlad lives in a house with index xx, and Nastya lives in a house with index yy. Vlad decided to visit Nastya. However, he remembered that he had postponed for later kk things that he has to do before coming to Nastya. To do the ii-th thing, he needs to come to the aiai-th house, things can be done in any order. In 11 minute, he can walk from one house to another if they are connected by a road.

Vlad does not really like walking, so he is interested what is the minimum number of minutes he has to spend on the road to do all things and then come to Nastya. Houses a1,a2,,ana1,a2,…,an he can visit in any order. He can visit any house multiple times (if he wants).

Vlad and Unfinished Business solution codeforces

The first line of input contains an integer tt (1t1041≤t≤104) — the number of input test cases. There is an empty line before each test case.

The first line of each test case contains two integers nn and kk (1kn21051≤k≤n≤2⋅105) — the number of houses and things, respectively.

The second line of each test case contains two integers xx and yy (1x,yn1≤x,y≤n) — indices of the houses where Vlad and Nastya live, respectively.

The third line of each test case contains kk integers a1,a2,,aka1,a2,…,ak (2ain2≤ai≤n) — indices of houses Vlad need to come to do things.

The following n1n−1 lines contain description of city, each line contains two integers vjvj and ujuj (1uj,vjn1≤uj,vj≤n) — indices of houses connected by road jj.

It is guaranteed that the sum of nn for all cases does not exceed 21052⋅105.

Vlad and Unfinished Business solution codeforces

Output tt lines, each of which contains the answer to the corresponding test case of input. As an answer output single integer — the minimum number of minutes Vlad needs on the road to do all the things and come to Nastya.

Example

input

Copy
3

3 1
1 3
2
1 3
1 2

6 4
3 5
1 6 2 1
1 3
3 4
3 5
5 6
5 2

6 2
3 2
5 3
1 3
3 4
3 5
5 6
5 2

Vlad and Unfinished Business solution codeforces

Copy
3
7
2
Note

Tree and best path for the first test case:

12131→2→1→3
Tree and best path for the second test case:

313525653→1→3→5→2→5→6→5
Tree and best path for the third test case:

352
 

Leave a Comment