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

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

Вам дано полное бинарное дерево$$$^\dagger$$$, состоящее из $$$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$$$ возможным порядком обхода в глубину$$$^\ddagger$$$ заданного дерева.

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

$$$^\dagger$$$ Полное бинарное дерево — это дерево с корнем в вершине $$$1$$$, имеющее размер $$$n=2^k-1$$$ для некоторого целого положительного числа $$$k$$$, и где родитель каждой вершины $$$i$$$ ($$$1<i\le n$$$) — это $$$\left\lfloor\frac{i}{2}\right\rfloor$$$. Таким образом, все листья этого дерева находятся на расстоянии $$$k - 1$$$ от корня.

$$$^\ddagger$$$ Порядок обхода в глубину получается вызовом следующей функции $$$\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$$$ ($$$3\le n\le 65\,535$$$, $$$2\le q\le 5 \cdot 10^4$$$) — количество вершин в дереве и количество запросов. Гарантируется, что $$$n=2^k-1$$$ для некоторого целого положительного числа $$$k$$$.

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

В следующей строке содержатся $$$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$$$ не превышает $$$65\,535$$$, а сумма всех $$$q$$$ не превышает $$$5 \cdot 10^4$$$.

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

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

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

Пример
Входные данные
2
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
Выходные данные
YES
YES
NO
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]$$$ соответственно.