Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Запросы на дереве
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Кто не работает, тот не ест. Получи то, что ты хочешь своими силами. Поверь, искренние и серьёзные люди всегда смеются последними. Но я всё равно не дам тебе подарка.
—Санта, Hayate no Gotoku!

Поскольку Хаяте не получил никаких рождественских подарков от Санты, его вместо этого ожидает решение задачи на запросы на дереве.

У Хаяте есть дерево с $$$n$$$ вершинами.

Теперь Хаяте хочет, чтобы вы ответили на $$$q$$$ запросов. Каждый запрос состоит из вершины $$$x$$$ и $$$k$$$ других дополнительных вершин $$$a_1,a_2,\ldots,a_k$$$. Эти $$$k+1$$$ вершина гарантированно различны.

Для каждого запроса необходимо найти длину самого длинного простого пути, начинающегося в вершине $$$x^\dagger$$$ после удаления вершин $$$a_1,a_2,\ldots,a_k$$$ вместе со всеми ребрами, соединенными хотя бы с одной из вершин $$$a_1,a_2,\ldots,a_k$$$.

$$$^\dagger$$$ Простой путь длины $$$k$$$, начинающийся в вершине $$$x$$$ — это последовательность различных вершин $$$x=u_0,u_1,\ldots,u_k$$$ таких, что существует ребро между вершинами $$$u_{i-1}$$$ и $$$u_i$$$ для всех $$$1 \leq i \leq k$$$.

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

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

Следующие $$$n - 1$$$ строк содержат по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — в дереве есть ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что заданные ребра образуют дерево.

Следующие $$$q$$$ строк описывают запросы. Каждая строка содержит целые числа $$$x$$$, $$$k$$$ и $$$a_1,a_2,\ldots,a_k$$$ ($$$1 \leq x \leq n$$$, $$$0 \leq k < n$$$, $$$1 \leq a_i \leq n$$$) — начальная вершина, количество удаленных вершин и удаленные вершины.

Гарантируется, что в запросе все вершины $$$x,a_1,a_2,\ldots,a_k$$$ различны.

Гарантируется, что сумма $$$k$$$ по всем запросам не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого запроса выведите одно целое число, являющееся ответом на этот запрос.

Примеры
Входные данные
7 7
1 2
1 3
3 4
2 5
2 6
6 7
2 0
2 1 1
2 2 1 6
3 1 4
3 1 1
5 0
5 2 1 6
Выходные данные
3
2
1
4
1
4
1
Входные данные
4 4
1 2
1 3
2 4
2 1 3
3 1 4
2 1 4
2 3 1 3 4
Выходные данные
1
2
2
0
Примечание

В первом примере дерево выглядит следующим образом:

В первом запросе ни одна вершина не пропущена. Самый длинный простой путь, начинающийся в вершине $$$2$$$, это $$$2 \to 1 \to 3 \to 4$$$. Таким образом, ответ — $$$3$$$.

Во третьем запросе отсутствуют вершины $$$1$$$ и $$$6$$$, и дерево показано ниже. Самый длинный простой путь из вершины $$$2$$$ — это $$$2 \to 5$$$. Таким образом, ответ — $$$1$$$.