E. Запросы на дереве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано корневое дерево, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Корень дерева находится в вершине с номером $$$1$$$.

Дерево — это связный неориентированный граф с $$$n-1$$$ ребром.

Вам заданы $$$m$$$ запросов. $$$i$$$-й запрос состоит из множества $$$k_i$$$ различных вершин $$$v_i[1], v_i[2], \dots, v_i[k_i]$$$. Ваша задача — определить, существует ли путь от корня до некоторой вершины $$$u$$$ такой, что каждая из заданных $$$k$$$ вершин или принадлежит этому пути, или расположена на расстоянии $$$1$$$ от некоторой вершины на этом пути.

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

Первая строка теста содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — количество вершин в дереве и количество запросов.

Каждая из следующих $$$n-1$$$ строк описывает ребро дерева. Ребро $$$i$$$ задается двумя целыми числами $$$u_i$$$ и $$$v_i$$$ — номерами вершин, которые это ребро соединяет $$$(1 \le u_i, v_i \le n, u_i \ne v_i$$$).

Гарантируется, что заданные ребра формируют дерево.

Следующие $$$m$$$ строк описывают запросы. $$$i$$$-я строка описывает $$$i$$$-й запрос и начинается с целого числа $$$k_i$$$ ($$$1 \le k_i \le n$$$) — количества вершин в текущем запросе. Затем следуют $$$k_i$$$ целых чисел: $$$v_i[1], v_i[2], \dots, v_i[k_i]$$$ ($$$1 \le v_i[j] \le n$$$), где $$$v_i[j]$$$ — это $$$j$$$-я вершина в $$$i$$$-м запросе.

Гарантируется, что все вершины в одном запросе различны.

Также гарантируется, что сумма всех $$$k_i$$$ не превосходит $$$2 \cdot 10^5$$$ ($$$\sum\limits_{i=1}^{m} k_i \le 2 \cdot 10^5$$$).

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

Для каждого запроса выведите ответ — «YES», если существует путь от корня до некоторой вершины $$$u$$$ такой, что каждая из $$$k$$$ заданных вершин или принадлежит этому пути, или расположена на расстоянии $$$1$$$ от какой-либо вершины на этом пути, и «NO» в противном случае.

Пример
Входные данные
10 6
1 2
1 3
1 4
2 5
2 6
3 7
7 8
7 9
9 10
4 3 8 9 10
3 2 4 6
3 2 1 5
3 4 8 2
2 6 10
3 5 4 7
Выходные данные
YES
YES
YES
YES
NO
NO
Примечание

Изображение, относящееся к примеру:

Рассмотрим запросы.

Первый запрос — $$$[3, 8, 9, 10]$$$. Ответ — «YES», так как вы можете выбрать путь от корня $$$1$$$ до вершины $$$u=10$$$. Тогда вершины $$$[3, 9, 10]$$$ принадлежат пути от $$$1$$$ до $$$10$$$ и вершина $$$8$$$ расположена на расстоянии $$$1$$$ от вершины $$$7$$$, которая также принадлежит этому пути.

Второй запрос — $$$[2, 4, 6]$$$. Ответ — «YES», так как вы можете выбрать путь до вершины $$$u=2$$$. Тогда вершина $$$4$$$ находится на расстоянии $$$1$$$ от вершины $$$1$$$, которая принадлежит этому пути, а вершина $$$6$$$ находится на расстоянии $$$1$$$ от вершины $$$2$$$, которая принадлежит этому пути.

Третий запрос — $$$[2, 1, 5]$$$. Ответ — «YES», так как вы можете выбрать путь до вершины $$$u=5$$$ и все вершины из запроса будут принадлежать этому пути.

Четвертый запрос — $$$[4, 8, 2]$$$. Ответ — «YES», так как вы можете выбрать путь до вершины $$$u=9$$$, и вершины $$$2$$$ и $$$4$$$ расположены на расстоянии $$$1$$$ от вершины $$$1$$$, которая принадлежит этому пути, а вершина $$$8$$$ расположена на расстоянии $$$1$$$ от вершины $$$7$$$, которая принадлежит этому пути.

Ответ и на пятый, и на шестой запросы — «NO», потому что вы не можете выбрать подходящую вершину $$$u$$$.