This is an easy version of the problem. The only difference between an easy and a hard version is in the number of queries.

Polycarp grew a tree from $n$ vertices. We remind you that a tree of $n$ vertices is an undirected connected graph of $n$ vertices and $n-1$ edges that does not contain cycles.

He calls a set of vertices passable if there is such a path in the tree that passes through each vertex of this set without passing through any edge twice. The path can visit other vertices (not from this set).

In other words, a set of vertices is called passable if there is a simple path that passes through all the vertices of this set (and possibly some other).

For example, for a tree below sets $\{3, 2, 5\}$, $\{1, 5, 4\}$, $\{1, 4\}$ are passable, and $\{1, 3, 5\}$, $\{1, 2, 3, 4, 5\}$ are not.

Polycarp asks you to answer $q$ queries. Each query is a set of vertices. For each query, you need to determine whether the corresponding set of vertices is passable.


-----Input-----

The first line of input contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — number of vertices.

Following $n - 1$ lines a description of the tree..

Each line contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) — indices of vertices connected by an edge.

Following line contains single integer $q$ ($1 \le q \le 5$) — number of queries.

The following $2 \cdot q$ lines contain descriptions of sets.

The first line of the description contains an integer $k$ ($1 \le k \le n$) — the size of the set.

The second line of the description contains $k$ of distinct integers $p_1, p_2, \dots, p_k$ ($1 \le p_i \le n$) — indices of the vertices of the set.

It is guaranteed that the sum of $k$ values for all queries does not exceed $2 \cdot 10^5$.


-----Output-----

Output $q$ lines, each of which contains the answer to the corresponding query. As an answer, output "YES" if the set is passable, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).


-----Examples-----

Input
5
1 2
2 3
2 4
4 5
5
3
3 2 5
5
1 2 3 4 5
2
1 4
3
1 3 5
3
1 5 4
Output
YES
NO
YES
NO
YES
Input
5
1 2
3 2
2 4
5 2
4
2
3 1
3
3 4 5
3
2 3 5
1
1
Output
YES
NO
YES
YES


-----Note-----

None

Difficulty: HARD
Tags: Tree algorithms

Graph traversal

Starter code:

Solutions:
import sys, threading

def main():
	n = int(input())
	graph = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
	q = int(input())
	for _ in range(q):
		input()
		queries = set(map(int, input().split()))
		root = node = list(queries)[0]
		visited = {root}
		counts = [0] * (n + 1)
		counts[node] = -1
		mels = [True]

		def dfs(node):
			ans = False
			count = 0
			for v in graph[node]:
				if v not in visited:
					visited.add(v)
					cur = dfs(v)
					if cur:
						count += 1
					if count > (2 if node == root else 1):
						mels[0] = False
					ans = ans or cur
			return ans or node in queries
		dfs(root)
		print('YES' if mels[0] else 'NO')
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


from collections import defaultdict, deque
from functools import lru_cache
from heapq import heappush, heappop

def input_int():
	return int(input())

def input_arr():
	return list(map(int, input().split()))

def input_tupple():
	return map(int, input().split())

def solution():
	n = input_int()
	graph = defaultdict(list)
	for _ in range(n - 1):
		(a, b) = input_tupple()
		graph[a].append(b)
		graph[b].append(a)
	t = input_int()
	for _ in range(t):
		input()
		arr = set(input_arr())

		def deepest(cur, parent):
			mx = 0
			node = cur if cur in arr else None
			for nbr in graph[cur]:
				if nbr == parent:
					continue
				(d, v) = deepest(nbr, cur)
				if v in arr and d > mx:
					mx = d
					node = v
			return (mx + 1, node)
		cur = arr.pop()
		arr.add(cur)
		(_, first) = deepest(cur, -1)

		def dfs(cur, parent):
			count = 0
			for nbr in graph[cur]:
				if nbr == parent:
					continue
				(ans, contain) = dfs(nbr, cur)
				count += contain
				if ans == False:
					return (False, 0)
			return (count < 2, count + (cur in arr) > 0)
		(ans, _) = dfs(first, -1)
		if ans:
			print('YES')
		else:
			print('NO')
import sys
import threading
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
thread = threading.Thread(target=solution)
thread.start()
thread.join()


import sys
from collections import defaultdict
from math import sqrt, ceil, floor, factorial, log
from bisect import bisect_left, bisect_right
from io import BytesIO, IOBase, StringIO
input = lambda : sys.stdin.readline().rstrip()
import threading

def main():

	def inlt():
		return list(map(int, input().split()))
	t = int(input())
	dic = defaultdict(list)
	for i in range(t - 1):
		(a, b) = map(int, input().split())
		dic[a].append(b)
		dic[b].append(a)
	root = 1
	q = int(input())

	def recur(root):
		visited.add(root)
		ans = 1 if s[root] > 0 else 0
		new = []
		for j in dic[root]:
			if j not in visited:
				vayu = recur(j)
				if vayu:
					new.append(vayu)
		if len(new) == 1:
			if new[0] + ans == len(lis):
				final[0] = True
			return new[0] + ans
		if len(new) == 2:
			if new[0] + new[1] + ans == len(lis):
				final[0] = True
			else:
				return 0
		if len(new) > 2:
			return 0
		if len(new) == 0:
			if ans == len(lis):
				final[0] = True
			return ans
	while q:
		q -= 1
		n = int(input())
		lis = inlt()
		visited = set()
		s = defaultdict(int)
		final = [False]
		for j in lis:
			s[j] += 1
		recur(1)
		print('YES') if final[0] else print('NO')
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()