← 返回题目列表

Codeforces · 1611/E1

E1. 逃离迷宫(简单版)

中文机器翻译题面 查看原题

与E2唯一的区别是问题的问题..

Vlad 用 $$$n$$$ 个房间和 $$$n-1$$$ 双向走廊建造了一个迷宫。从任何房间 $$$u$$$ 到任何其他房间 $$$v$$$ 都可以通过一系列走廊到达。这样,房间系统就形成了一棵无向树。

Vlad 邀请 $$$k$$$ 朋友和他们一起玩游戏。

Vlad 在 $$$1$$$ 房间开始游戏,如果他到达 $$$1$$$ 以外的房间(恰好有一条走廊通向该房间),则获胜。

朋友被放置在迷宫中:编号为 $$$i$$$ 的朋友在房间 $$$x_i$$$ 中,并且没有两个朋友在同一个房间中(即,对于所有 $$$i \neq j$$$,$$$x_i \neq x_j$$$)。如果朋友中的一个人在弗拉德获胜之前在任何房间或走廊遇到他,那么他就获胜。

在一个单位时间内,每个游戏参与者可以通过一条走廊。所有参与者同时移动。参与者不得移动。每个房间可同时容纳所有参与者。

朋友们知道迷宫的设计并打算获胜。弗拉德有点害怕他们的热情。确定他是否能保证胜利(即他能以朋友玩的任何方式获胜)。

换句话说,确定是否存在这样一个 Vlad 的动作序列,可以让 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 能够保证自己获胜,则测试用例的答案应该是“YES”,否则应该是“NO”。

您可以按照您想要的任何大小写打印每个字母(因此,例如,字符串“yEs”、“yes”、“Yes”和“YES”都将被识别为肯定答案)。

示例

输入 #1

4

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

3 1
2
1 2
2 3

3 1
2
1 2
1 3

3 2
2 3
3 1
1 2

输出 #1

YES
NO
YES
NO

注意

在第一个测试用例中,无论他的朋友的策略如何,Vlad 都可以通过进入 $$$4$$$ 房间获胜。游戏可能是这样的:

弗拉德和朋友们原来的地点。弗拉德被标记为绿色,朋友们——被标记为红色。

一个时间单位后的位置。

游戏结束。

请注意,如果 Vlad 试图到达 $$$8$$$ 房间的出口,那么来自 $$$3$$$ 房间的朋友将能够抓住他。