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

D2. Проверка DFS (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. В этой версии на заданное дерево нет дополнительных ограничений, а ограничения на $$$n$$$ и $$$q$$$ выше. Вы можете совершать взломы только в том случае, если решены обе версии задачи.

Вам дано корневое дерево, состоящее из $$$n$$$ вершин. Вершины пронумерованы от $$$1$$$ до $$$n$$$, вершина $$$1$$$ — корень. Вам также дана перестановка $$$p_1, p_2, \ldots, p_n$$$ чисел $$$[1,2,\ldots,n]$$$.

Вам нужно ответить на $$$q$$$ запросов. В каждом запросе вам даются два целых числа $$$x$$$, $$$y$$$; вам нужно поменять местами $$$p_x$$$ и $$$p_y$$$ и определить, является ли $$$p_1, p_2, \ldots, p_n$$$ возможным порядком обхода в глубину$$$^\dagger$$$ заданного дерева.

Обратите внимание, что перестановки элементов сохраняются между запросами.

$$$^\dagger$$$ Порядок обхода в глубину получается вызовом следующей функции $$$\texttt{dfs}$$$ на заданном дереве.

dfs_order = []

function dfs(v):
    добавить v в конец dfs_order
    выбрать произвольную перестановку s детей v
    for child in s:
         dfs(child)

dfs(1)

Обратите внимание, что порядок обхода DFS определён не однозначно.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

В следующей строке содержатся $$$n-1$$$ целых чисел $$$a_2,a_3,\ldots,a_n$$$ ($$$1\le a_i<i$$$) — родитель каждой вершины в заданном дереве.

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

В следующих $$$q$$$ строках каждая строка содержит два целых числа $$$x$$$, $$$y$$$ ($$$1\le x,y\le n,x\neq y$$$) — позиции элементов, которые нужно поменять местами в перестановке.

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

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

Для каждого набора входных данных выведите $$$q$$$ строк, соответствующих $$$q$$$ запросам. Для каждого запроса выведите $$$\texttt{YES}$$$, если есть порядок обхода в глубину, который точно равен текущей перестановке, и выведите $$$\texttt{NO}$$$ в противном случае.

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

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

В первом наборе входных данных перестановка $$$p_1, p_2, \ldots, p_n$$$ после каждой модификации равна $$$[1,3,2],[1,2,3],[3,2,1]$$$ соответственно. Первые две перестановки — это возможные порядки обхода в глубину; третья — не порядок обхода в глубину.

Во втором наборе входных данных перестановка $$$p_1, p_2, \ldots, p_n$$$ после каждой модификации равна $$$[1,2,3,4,5,6,7],[1,2,5,4,3,6,7],[1,3,5,4,2,6,7],[1,3,7,4,2,6,5],[1,3,7,6,2,4,5]$$$ соответственно.