The only difference with E2 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. Vlad is a bit afraid of their ardor. Determine if he can guarantee victory (i.e. can he win in any way friends play).

In other words, determine if there is such a sequence of Vlad's moves that lets Vlad win in any way friends play.


-----Input-----

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-----

Print $t$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be "YES" if Vlad can guarantee himself a victory and "NO" otherwise.

You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" will all be recognized as positive answers).


-----Examples-----

Input
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
Output
YES
NO
YES
NO


-----Note-----

In the first test case, regardless of the strategy of his friends, Vlad can win by going to room $4$. The game may look like this:

The original locations of Vlad and friends. Vlad is marked in green, friends — in red.

Locations after one unit of time.

End of the game.

Note that if Vlad tries to reach the exit at the room $8$, then a friend from the $3$ room will be able to catch him.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph traversal

Shortest paths

Amortized analysis

Greedy algorithms

Tree algorithms


Solutions:
import sys
from collections import deque
t = int(sys.stdin.readline())
for _ in range(t):
	empty = sys.stdin.readline()
	(n, k) = map(int, sys.stdin.readline().split())
	x = list(map(int, sys.stdin.readline().split()))
	conn = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(v, u) = map(int, sys.stdin.readline().split())
		conn[v].append(u)
		conn[u].append(v)
	check = [n for i in range(n + 1)]
	q = deque()
	for friend in x:
		q.append(friend)
		check[friend] = 0
	while q:
		pos = q.popleft()
		for nextPos in conn[pos]:
			if check[nextPos] < n:
				continue
			q.append(nextPos)
			check[nextPos] = check[pos] + 1
	q = deque()
	q.append(1)
	visit = [n for i in range(n + 1)]
	visit[1] = 0
	answer = 'NO'
	while q:
		pos = q.popleft()
		if pos != 1 and len(conn[pos]) == 1:
			answer = 'YES'
			break
		for nextPos in conn[pos]:
			if visit[nextPos] < n:
				continue
			elif visit[pos] + 1 >= check[nextPos]:
				continue
			q.append(nextPos)
			visit[nextPos] = visit[pos] + 1
	print(answer)


import threading
import sys
threading.stack_size(10 ** 8)
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop, heapify

def main():
	for _ in range(int(input())):
		input()
		(n, k) = map(int, input().split())
		k = [int(i) for i in input().split()]
		ck = Counter(k)
		c = [float('inf')] * (n + 1)
		g = [[] for _ in range(n + 1)]
		for _ in range(n - 1):
			(u, v) = map(int, input().split())
			g[u].append(v)
			g[v].append(u)

		def dfs(cn, p):
			if ck[cn] == 1:
				c[cn] = 0
				return c[cn]
			for nn in g[cn]:
				if nn != p:
					c[cn] = min(c[cn], 1 + dfs(nn, cn))
			return c[cn]
		dfs(1, -1)
		global pos
		pos = False

		def pepega(cn, p, cd):
			global pos
			if cd >= c[cn]:
				return
			if len(g[cn]) == 1 and cn != 1:
				pos = True
				return
			for nn in g[cn]:
				if nn != p:
					pepega(nn, cn, cd + 1)
		pepega(1, -1, 0)
		if pos:
			print('YES')
		else:
			print('NO')
threading.Thread(target=main).start()


def f():
	input()
	(n, k) = map(int, input().split())
	visv = set([i - 1 for i in map(int, input().split())])
	g = [set() for i in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		g[a - 1].add(b - 1)
		g[b - 1].add(a - 1)
	qv = set() | visv
	qh = set([0])
	vish = set()
	while 1:
		if not qh:
			return 'NO'
		nqh = set()
		for i in qh:
			vish.add(i)
			if len(g[i]) == 1 and i:
				return 'YES'
			for j in g[i]:
				if j not in vish and j not in visv:
					nqh.add(j)
		nqv = set()
		for i in qv:
			for j in g[i]:
				if j not in visv:
					nqv.add(j)
					visv.add(j)
		qh = nqh - nqv
		qv = nqv
for _ in range(int(input())):
	print(f())


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
for _ in range(I()):
	s = S()
	(n, k) = M()
	a = L()
	adj = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = M()
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)

	def bfs(i):
		q = deque()
		v = [0] * n
		v[i] = 1
		for j in a:
			q.append([j - 1, j - 1])
			v[j - 1] = 1
		q.append([i, i])
		while q:
			(r, p) = q.popleft()
			if r != 0 and p == 0 and (len(adj[r]) == 1):
				return True
			for j in adj[r]:
				if v[j] == 0:
					v[j] = 1
					q.append([j, p])
		return False
	print('YES' if bfs(0) else 'NO')


from collections import *

def dfs():
	while qF and qP:
		for _ in range(len(qP)):
			curr = qP.popleft()
			if curr in visitedF:
				continue
			if len(corridors[curr]) == 1 and corridors[curr][0] in visitedP:
				return 'YES'
			for child in corridors[curr]:
				if child not in visitedP:
					qP.append(child)
					visitedP.add(child)
		for _ in range(len(qF)):
			curr = qF.popleft()
			for child in corridors[curr]:
				if child not in visitedF:
					qF.append(child)
					visitedF.add(child)
	return 'NO'
t = int(input())
for _ in range(t):
	input()
	(rooms, friends) = map(int, input().split())
	fr = list(map(int, input().split()))
	visitedF = set(fr)
	visitedP = set([1])
	qF = deque(fr)
	qP = deque([1])
	corridors = defaultdict(list)
	for _ in range(rooms - 1):
		(a, b) = map(int, input().split())
		corridors[a].append(b)
		corridors[b].append(a)
	print(dfs())


from collections import deque
t = int(input())
for _ in range(t):
	input()
	(rooms, friends) = [int(x) for x in input().strip().split()]
	mq = deque()
	visited: list = [False] * rooms
	rooms_with_friends: list = [int(x) - 1 for x in input().strip().split()]
	for room in rooms_with_friends:
		visited[room] = None
		mq.appendleft(room)
	visited[0] = True
	mq.appendleft(0)
	adj: list = [[] for _ in range(rooms)]
	for _ in range(rooms - 1):
		(a, b) = [int(x) - 1 for x in input().strip().split()]
		adj[a].append(b)
		adj[b].append(a)
	while mq:
		cur = mq.pop()
		for nxt in adj[cur]:
			if visited[nxt] == False:
				visited[nxt] = visited[cur]
				mq.appendleft(nxt)
	found: bool = False
	for i in range(1, rooms):
		if visited[i] and len(adj[i]) == 1:
			found = True
			break
	print('YES' if found else 'NO')


from collections import defaultdict, deque
t = int(input())
input()
for z in range(t):
	(rooms, friends_size) = list(map(int, input().split()))
	friends = list(map(int, input().split()))
	graph = defaultdict(list)
	for i in range(rooms - 1):
		(u, v) = list(map(int, input().split()))
		graph[u].append(v)
		graph[v].append(u)
	queue = deque([1])
	friends_queue = deque(friends)
	visited = set(friends)
	visited_me = set([1])
	can = False
	while len(queue) and len(friends_queue):
		size = len(queue)
		len_f = len(friends_queue)
		for a in range(len_f):
			node = friends_queue.popleft()
			for ngh in graph[node]:
				if ngh not in visited:
					visited.add(ngh)
					friends_queue.append(ngh)
		for p in range(size):
			node = queue.popleft()
			for ngh in graph[node]:
				if ngh not in visited_me and ngh not in visited:
					visited_me.add(ngh)
					queue.append(ngh)
			if len(graph[node]) == 1 and node != 1:
				can = True
	if can:
		print('YES')
	else:
		print('NO')
	if z != t - 1:
		input()


from collections import deque
t = int(input().strip())
for _ in range(t):
	_ = input()
	(n, k) = map(int, input().strip().split())
	adj = [[] for _ in range(n)]
	visited = [False for _ in range(n)]
	q = deque()
	for x in input().strip().split():
		temp = int(x) - 1
		q.append((temp, 0))
		visited[temp] = True
	q.append((0, 1))
	for _ in range(n - 1):
		(s, e) = map(lambda x: int(x) - 1, input().strip().split())
		adj[s].append(e)
		adj[e].append(s)
	reaches_leaf = False
	while len(q) > 0:
		(node, person) = q.popleft()
		if person == 1 and len(adj[node]) == 1 and (node != 0):
			reaches_leaf = True
			break
		for adjacent in adj[node]:
			if not visited[adjacent]:
				q.append((adjacent, person))
				visited[adjacent] = True
	if reaches_leaf:
		print('YES')
	else:
		print('NO')


from collections import defaultdict, deque
t = int(input())
for _ in range(t):
	input()
	(n, k) = map(int, input().split())
	rooms = list(map(int, input().split()))
	tree = defaultdict(list)
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		tree[u].append(v)
		tree[v].append(u)
	visited = set(rooms)
	visited.add(1)
	que = deque(list(map(lambda x: (x, True), rooms)) + [(1, False)])
	can_win = False
	while que:
		(r, is_friend) = que.popleft()
		for nei in tree[r]:
			if nei not in visited:
				if not is_friend and len(tree[nei]) == 1:
					can_win = True
					break
				visited.add(nei)
				que.append((nei, is_friend))
	if can_win:
		print('YES')
	else:
		print('NO')


from collections import defaultdict

def solve(n, k, froom, adj):
	fvisited = set()
	fvisited.add(1)
	for r in froom:
		fvisited.add(r)
	vroom = [1]
	leafs = set()
	for i in range(1, n + 1):
		if len(adj[i]) == 1:
			leafs.add(i)
	leafs.discard(1)
	while len(fvisited) < n:
		nfroom = []
		for r in froom:
			for val in adj[r]:
				if val not in fvisited:
					fvisited.add(val)
					nfroom.append(val)
		froom = nfroom
		nvroom = []
		for r in vroom:
			for val in adj[r]:
				if val not in fvisited:
					if val in leafs:
						return 'YES'
					fvisited.add(val)
					nvroom.append(val)
		if not nvroom:
			return 'NO'
		vroom = nvroom
	return 'NO'
for _ in range(int(input())):
	input()
	(n, k) = map(int, input().split())
	froom = list(map(int, input().split()))
	adj = defaultdict(list)
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		adj[b].append(a)
	print(solve(n, k, froom, adj))


def solve():
	input()
	(n, k) = map(int, input().split())
	f = list(enumerate(list(map(lambda x: int(x) - 1, input().split()))))
	g = {i: [] for i in range(n)}
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		g[a].append(b)
		g[b].append(a)
	needed = {}
	vlad = [0]
	visited = [False] * n
	friends = [-1] * n
	while len(vlad):
		nf = []
		for (i, f1) in f:
			if friends[f1] != -1:
				continue
			friends[f1] = i
			for e in g[f1]:
				nf.append((i, e))
		f = nf
		new_vlad = []
		for v in vlad:
			if friends[v] != -1:
				needed[friends[v]] = True
				continue
			if visited[v] == True:
				continue
			visited[v] = True
			if len(g[v]) == 1 and v != 0:
				return -1
			for e in g[v]:
				new_vlad.append(e)
		vlad = new_vlad
	return len(needed)
n = int(input())
for i in range(n):
	print('YES' if solve() == -1 else 'NO')


for t in range(int(input())):
	input()
	(n, k) = map(int, input().split())
	pos = set(map(int, input().split()))
	adj = [set() for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u].add(v)
		adj[v].add(u)
	player = set([1])
	friends = set() | pos
	vis = set()
	forb = set() | pos
	ok = False
	while 1:
		if not player:
			break
		player_nxt = set()
		for i in player:
			vis.add(i)
			if len(adj[i]) == 1 and i != 1:
				ok = True
				break
			for j in adj[i]:
				if j not in vis and j not in forb:
					player_nxt.add(j)
		if ok == True:
			break
		friends_nxt = set()
		for i in friends:
			for j in adj[i]:
				if j not in vis:
					vis.add(j)
					forb.add(j)
					friends_nxt.add(j)
		player = player_nxt - friends_nxt
		friends = friends_nxt
		if ok == True:
			break
	print('YES' if ok == True else 'NO')


from collections import deque
t = int(input())
for _ in range(t):
	input()
	(rooms, friends) = [int(x) for x in input().split()]
	q = deque([(int(x) - 1, 0) for x in input().split()])
	q.append((0, 1))
	adj = [[] for _ in range(rooms)]
	visited = set()
	vlad = False
	for i in range(rooms - 1):
		(a, b) = [int(x) - 1 for x in input().split()]
		adj[a].append(b)
		adj[b].append(a)
	while q:
		(curr, ppl) = q.popleft()
		if curr in visited:
			continue
		visited.add(curr)
		if ppl == 1 and len(adj[curr]) == 1 and (curr != 0):
			vlad = True
			break
		for a in adj[curr]:
			q.append((a, ppl))
	if vlad:
		print('YES')
	else:
		print('NO')


from collections import deque, defaultdict
for _ in range(int(input())):
	adf = input()
	(n, k) = list(map(int, input().split()))
	graph = defaultdict(list)
	visited = set()
	friends_visited = set()
	q = deque()
	for friend in list(map(int, input().split())):
		q.append((friend, 0))
		friends_visited.add(friend)
	q.append((1, 1))
	visited.add(1)
	for _ in range(n - 1):
		(a, b) = list(map(int, input().split()))
		graph[a].append(b)
		graph[b].append(a)
	found = 0
	while q:
		for _ in range(len(q)):
			(room, p) = q.popleft()
			if p == 1 and room in friends_visited:
				continue
			elif room != 1 and p == 1 and (len(graph[room]) == 1) and (room not in friends_visited):
				found = 1
				break
			for v in graph[room]:
				if v not in visited and v not in friends_visited:
					if not p:
						friends_visited.add(v)
					else:
						visited.add(v)
					q.append((v, 1 if p else 0))
		if found:
			break
	print('NO' if not found else 'YES')


import sys

def findpaths(mypos: list, paths):
	queue = mypos.copy()
	times = [-1] * n
	for i in mypos:
		times[i] = 0
	q = 0
	while q < len(queue):
		pos = queue[q]
		dirs = paths[pos]
		for i in dirs:
			if times[i] == -1:
				queue.append(i)
				times[i] = times[pos] + 1
		q += 1
	return times
for _ in range(int(sys.stdin.readline())):
	sys.stdin.readline()
	(n, k) = [int(x) for x in sys.stdin.readline().split()]
	friendposes = [int(x) - 1 for x in sys.stdin.readline().split()]
	paths = {i: [] for i in range(n)}
	for i in range(n - 1):
		(v, u) = [int(x) - 1 for x in sys.stdin.readline().split()]
		paths[v].append(u)
		paths[u].append(v)
	vlad = findpaths([0], paths)
	friends = findpaths(friendposes, paths)
	endposes = []
	for i in range(1, n):
		if len(paths[i]) == 1:
			endposes.append(i)
	won = any([vlad[endpos] < friends[endpos] for endpos in endposes])
	print('YNEOS'[1 - won::2])


from collections import deque
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	input()
	(n, k) = map(int, input().split())
	enemy = list(map(int, input().split()))
	node = [[-1, -1] for _ in range(n + 1)]
	edge = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		edge[a].append(b)
		edge[b].append(a)

	def bfs(li, mask):
		visited = [False] * (n + 1)
		q = deque()
		for t in li:
			visited[t] = True
			q.append((t, 1))
			node[t][mask] = 1
		while q:
			(v, cnt) = q.popleft()
			for w in edge[v]:
				if visited[w]:
					continue
				visited[w] = True
				node[w][mask] = cnt + 1
				q.append((w, cnt + 1))
	bfs(enemy, 0)
	bfs([1], 1)
	flg = False
	for (idx, t) in enumerate(node):
		if t[0] > t[1] and idx > 1 and (len(edge[idx]) == 1):
			flg = True
	print('YES' if flg else 'NO')


from collections import deque

def BFSDistance(graph, queue, reach):
	while len(queue) > 0:
		currentNode = queue.popleft()
		children = graph[currentNode]
		for child in children:
			if reach[child] == -1:
				reach[child] = reach[currentNode]
				queue.append(child)

def helper(graph, n, queue, reach):
	queue.append(0)
	reach[0] = 1
	BFSDistance(graph, queue, reach)
	for i in range(1, n):
		if len(graph[i]) == 1 and reach[i] == 1:
			return 'YES'
	return 'NO'
tests = int(input())
for i in range(tests):
	graph = {}
	tempStr = input()
	(n, k) = list(map(int, input().split()))
	location = list(map(int, input().split()))
	(queue, reach) = (deque(), [-1 for i in range(n)])
	for loc in location:
		queue.append(loc - 1)
		reach[loc - 1] = 0
	for i in range(n - 1):
		(a, b) = list(map(int, input().split()))
		if a - 1 in graph:
			graph[a - 1].append(b - 1)
		else:
			graph[a - 1] = [b - 1]
		if b - 1 in graph:
			graph[b - 1].append(a - 1)
		else:
			graph[b - 1] = [a - 1]
	ans = helper(graph, n, queue, reach)
	print(ans)


from collections import defaultdict, deque

def solve():
	input()
	(num_rooms, num_players) = list(map(int, input().split()))
	players_pos = list(map(int, input().split()))
	graph = defaultdict(set)
	for _ in range(num_rooms - 1):
		(u, v) = list(map(int, input().split()))
		graph[u].add(v)
		graph[v].add(u)
	leaves = {node: float('inf') for node in graph if len(graph[node]) == 1 and node != 1}
	(queue, visited) = (deque([]), set())
	for node_pos in players_pos:
		queue.append([node_pos, 0])
	while queue:
		for _ in range(len(queue)):
			(node, dist_from_player) = queue.popleft()
			if node in visited:
				continue
			else:
				visited.add(node)
			if node in leaves:
				leaves[node] = dist_from_player
			for nei in graph[node]:
				queue.append([nei, dist_from_player + 1])
	(vlad_q, visited) = (deque([[1, 0]]), set())
	while vlad_q:
		(cur_pos, dist_from_root) = vlad_q.popleft()
		if cur_pos in visited:
			continue
		else:
			visited.add(cur_pos)
		if cur_pos in leaves and dist_from_root < leaves[cur_pos]:
			return True
		for nei in graph[cur_pos]:
			vlad_q.append([nei, dist_from_root + 1])
	return False
for _ in range(int(input())):
	if solve():
		print('YES')
	else:
		print('NO')


from collections import defaultdict, deque

def answer(friends, hashmap):
	(queue, maxi) = (deque(), defaultdict(lambda : float('inf')))
	for i in friends:
		queue.append((i, 0))
	while queue:
		(node, travel) = queue.popleft()
		if travel >= maxi[node]:
			continue
		maxi[node] = min(maxi[node], travel)
		for nei in hashmap[node]:
			queue.append((nei, travel + 1))
	visited = set()
	queue.append((1, 0))
	while queue:
		(node, travel) = queue.popleft()
		if node != 1 and len(hashmap[node]) == 1 and (travel < maxi[node]):
			return 'YES'
		visited.add(node)
		for nei in hashmap[node]:
			if nei not in visited:
				queue.append((nei, travel + 1))
	return 'NO'
test = int(input())
for i in range(test):
	hashmap = defaultdict(list)
	input()
	first = list(map(int, input().split()))
	second = list(map(int, input().split()))
	for j in range(first[0] - 1):
		third = list(map(int, input().split()))
		hashmap[third[0]].append(third[1])
		hashmap[third[1]].append(third[0])
	print(answer(second, hashmap))


from collections import defaultdict
import heapq
from math import inf

def cf756e1(n, friends, graph):
	friendsMinTime = [inf for _ in range(n)]
	friendsReach = [(0, friend) for friend in friends]
	heapq.heapify(friendsReach)
	while friendsReach:
		(time, root) = heapq.heappop(friendsReach)
		if friendsMinTime[root - 1] <= time:
			continue
		friendsMinTime[root - 1] = time
		for node in graph[root]:
			if time + 1 < friendsMinTime[node - 1]:
				heapq.heappush(friendsReach, (time + 1, node))
	visited = set([1])
	locations = [(1, i) for i in graph[1]]
	heapq.heapify(locations)
	while locations:
		(time, root) = heapq.heappop(locations)
		if friendsMinTime[root - 1] <= time:
			continue
		if len(graph[root]) == 1:
			return True
		visited.add(root)
		for node in graph[root]:
			if node not in visited:
				heapq.heappush(locations, (time + 1, node))
	return False
for _ in range(int(input())):
	input()
	(n, k) = map(int, input().split())
	friends = list(map(int, input().split()))
	graph = defaultdict(list)
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	print('YES' if cf756e1(n, friends, graph) else 'NO')