E2. Побег из лабиринта (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эта задача отличается от E1 только поставленным вопросом.

Влад построил лабиринт из $$$n$$$ комнат и $$$n-1$$$ двунаправленного коридора. Из любой комнаты $$$u$$$ по коридорам достижима любая другая комната $$$v$$$. Таким образом, система комнат образует неориентированное дерево.

Влад собрал $$$k$$$ друзей, чтобы сыграть с ними в игру.

Влад начинает игру в комнате с номером $$$1$$$ и выигрывает, если доходит до комнаты, отличной от $$$1$$$, в которую ведёт ровно один коридор. Друзья же расставлены по лабиринту — друг с номером $$$i$$$ стоит в комнате $$$x_i$$$, и никакие два друга не стоят в одной комнате (то есть $$$x_i \neq x_j$$$ для всех $$$i \neq j$$$). Друзья выигрывают, если одному удаётся встретиться с Владом в какой-либо комнате или коридоре, до того как он выиграет.

За одну единицу времени каждый участник игры может пройти по одному коридору. Все участники ходят одновременно. Участники также могут не двигаться. Каждая комната может вместить всех участников одновременно.

Друзья досконально изучили план и намерены выиграть. Также они не хотят зря тратить силы и просят вас определить, могут ли они выиграть и, если могут, какое минимальное количество друзей должно остаться в лабиринте, чтобы они всегда могли поймать Влада.

Иными словами вам нужно определить размер минимального подмножества друзей, который сможет переиграть Влада или сказать что такого подмножества не существует.

Входные данные

В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте. Перед каждым набором входных данных в тесте содержится пустая строка.

Первая строка набора входных данных содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le k < 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$$$.

Выходные данные

Выведите $$$t$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите $$$-1$$$, если Влад в любом случае победит, и минимальное необходимое число друзей иначе.

Пример
Входные данные
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
Выходные данные
-1
2
1
2
Примечание

В первом наборе входных данных даже если все друзья останутся в лабиринте, Влад всё равно сможет выиграть. Поэтому ответ «-1».

Во втором наборе входных данных достаточно оставить друзей из комнат $$$6$$$ и $$$7$$$. Тогда Влад не сможет выиграть. Ответ «2».

Во третьем и четвертом наборах входных данных Влад не сможет выиграть только если все его друзья останутся в лабиринте. Поэтому ответы соответственно «1» и «2».