与E1唯一的区别是问题的问题。
Vlad 用 $$$n$$$ 个房间和 $$$n-1$$$ 双向走廊建造了一个迷宫。从任何房间 $$$u$$$ 到任何其他房间 $$$v$$$ 都可以通过一系列走廊到达。这样,房间系统就形成了一棵无向树。
Vlad 邀请 $$$k$$$ 朋友和他们一起玩游戏。
Vlad 在 $$$1$$$ 房间开始游戏,如果他到达 $$$1$$$ 以外的房间(恰好有一条走廊通向该房间),则获胜。将朋友放置在迷宫中:编号为 $$$i$$$ 的朋友在 $$$x_i$$$ 房间中,并且没有两个朋友在同一个房间中(即,对于所有 $$$i \neq j$$$,$$$x_i \neq x_j$$$)。如果朋友中的一个人在弗拉德获胜之前在任何房间或走廊遇到他,那么他就获胜。
在一个单位时间内,每个游戏参与者可以通过一条走廊。所有参与者同时移动。参与者不得移动。每个房间可同时容纳所有参与者。
朋友们知道迷宫的设计并打算获胜。他们不想浪费太多的精力。他们要求你确定他们是否可以获胜,如果可以,迷宫中必须保留最少数量的朋友,以便他们总能抓住弗拉德。
换句话说,你需要确定能够抓住 Vlad 的朋友的最小子集(通过元素数量)的大小,或者说这样的子集不存在。
输入
输入的第一行包含一个整数 $$$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$$$ 行,每行包含相应测试用例的答案。如果 Vlad 无论如何都会获胜,则测试用例的答案应该是 $$$-1$$$,否则,朋友数量最少。
示例
输入 #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
-1 2 1 2
注意
在第一组输入中,即使所有朋友都留在迷宫中,Vlad 仍然可以获胜。因此,答案是“-1”。
在第二组输入中,离开 $$$6$$$ 和 $$$7$$$ 房间的朋友就足够了。那么弗拉德将无法获胜。答案是“2”。
在第三组和第四组输入中,只有所有朋友都留在迷宫中,Vlad 才能获胜。因此答案是“1”和“2”。