G. Необычное развлечение
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дерево — связный граф без циклов.

Перестановка — массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[5, 1, 3, 2, 4]$$$ является перестановкой, но $$$[2, 1, 1]$$$ не является перестановкой ($$$1$$$ встречается в массиве дважды) и $$$[1, 3, 2, 5]$$$ тоже не является перестановкой ($$$n = 4$$$, но в массиве присутствует $$$5$$$).

После неудачной съёмки в ролике BrMeast у Лёши началась депрессия. Даже день рождения не радовал его. Однако после подарка Тимофея настроение Лёши резко поднялось. Теперь он днями напролёт игрался с подаренным конструктором. Недавно он придумал себе необычное развлечение.

Лёша строит из своего конструктора дерево, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, с корнем в вершине $$$1$$$. Затем он в произвольном порядке выписывает каждое число от $$$1$$$ до $$$n$$$ ровно по одному разу и получает перестановку $$$p$$$. После этого Лёша придумывает $$$q$$$ троек чисел $$$l, r, x$$$. Для каждой тройки он пытается понять, есть ли среди вершин с номерами $$$p_l, p_{l+1}, \ldots, p_r$$$ хотя бы один потомок вершины $$$x$$$.

Вершина $$$u$$$ является потомком вершины $$$v$$$ тогда и только тогда, когда $$$\mathrm{dist}(1, v) + \mathrm{dist}(v, u) = \mathrm{dist}(1, u)$$$, где $$$\mathrm{dist}(a, b)$$$ — расстояние между вершинами $$$a$$$ и $$$b$$$. Иначе говоря, вершина $$$v$$$ должна находиться на пути от корня до вершины $$$u$$$.

Лёша рассказал об этом развлечении Захару. Теперь Лёша говорит своему другу $$$q$$$ троек, описанных выше, надеясь, что Захар сможет проверить наличие потомка. Захар очень сильно хочет спать, поэтому обратился за помощью к вам. Помогите Захару ответить на все вопросы Лёши и наконец-то пойти спать.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных дано два целых числа $$$n, q$$$ ($$$1 \le n, q \le 10^5$$$) — количество вершин в дереве и количество вопросов, соответственно.

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

В следующей строке даны $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — перестановка $$$p$$$ (гарантируется, что каждое число от $$$1$$$ до $$$n$$$ встречается ровно один раз).

Далее следуют $$$q$$$ строк, описывающие вопросы Лёши. В $$$i$$$-й строке написаны числа $$$l, r, x$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le x \le n$$$), описанные в условии.

Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превышают $$$10^5$$$.

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

Для каждого вопроса Лёши выведите «Yes» (без кавычек), если описанный в условии потомок существует, иначе выведите «No» (без кавычек).

Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).

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

NO
YES
YES
YES
NO
YES
YES
NO
NO
NO

YES