DFS Checker (Easy Version)
Description
This is the easy version of the problem. In this version, the given tree is a perfect binary tree and the constraints on $n$ and $q$ are lower. You can make hacks only if both versions of the problem are solved.
You are given a perfect binary tree$^\dagger$ consisting of $n$ vertices. The vertices are numbered from $1$ to $n$, and the root is the vertex $1$. You are also given a permutation $p_1, p_2, \ldots, p_n$ of $[1,2,\ldots,n]$.
You need to answer $q$ queries. For each query, you are given two integers $x$, $y$; you need to swap $p_x$ and $p_y$ and determine if $p_1, p_2, \ldots, p_n$ is a valid DFS order$^\ddagger$ of the given tree.
Please note that the swaps are persistent through queries.
$^\dagger$ A perfect binary tree is a tree with vertex $1$ as its root, with size $n=2^k-1$ for a positive integer $k$, and where the parent of each vertex $i$ ($1<i\le n$) is $\left\lfloor\frac{i}{2}\right\rfloor$. Thus, all leaves of this tree are at a distance $k - 1$ from the root.
$^\ddagger$ A DFS order is found by calling the following $\texttt{dfs}$ function on the given tree.
dfs_order = []
function dfs(v):
append v to the back of dfs_order
pick an arbitrary permutation s of children of v
for child in s:
dfs(child)
dfs(1)
Note that the DFS order is not unique.
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le10^4$). The description of the test cases follows.
The first line of each test case contains two integers $n$, $q$ ($3\le n\le 65\,535$, $2\le q\le 5 \cdot 10^4$) — the number of vertices in the tree and the number of queries. It is guaranteed that $n=2^k-1$ for a positive integer $k$.
The next line contains $n-1$ integers $a_2,a_3,\ldots,a_n$ ($1\le a_i<i$) — the parent of each vertex in the given tree. It is guaranteed that $a_i=\left\lfloor\frac{i}{2}\right\rfloor$.
The next line contains $n$ integers $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, all $p_i$ are distinct) — the initial permutation $p$.
The next $q$ lines each contain two integers $x$, $y$ ($1\le x,y\le n,x\neq y$) — the positions of the elements to swap in the permutation.
It is guaranteed that the sum of all $n$ does not exceed $65\,535$, and the sum of all $q$ does not exceed $5 \cdot 10^4$.
For each test case, print $q$ lines corresponding to the $q$ queries. For each query, output $\texttt{YES}$ if there is a DFS order that exactly equals the current permutation, and output $\texttt{NO}$ otherwise.
You can output $\texttt{Yes}$ and $\texttt{No}$ in any case (for example, strings $\texttt{yEs}$, $\texttt{yes}$, $\texttt{Yes}$ and $\texttt{YES}$ will be recognized as a positive response).
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le10^4$). The description of the test cases follows.
The first line of each test case contains two integers $n$, $q$ ($3\le n\le 65\,535$, $2\le q\le 5 \cdot 10^4$) — the number of vertices in the tree and the number of queries. It is guaranteed that $n=2^k-1$ for a positive integer $k$.
The next line contains $n-1$ integers $a_2,a_3,\ldots,a_n$ ($1\le a_i<i$) — the parent of each vertex in the given tree. It is guaranteed that $a_i=\left\lfloor\frac{i}{2}\right\rfloor$.
The next line contains $n$ integers $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, all $p_i$ are distinct) — the initial permutation $p$.
The next $q$ lines each contain two integers $x$, $y$ ($1\le x,y\le n,x\neq y$) — the positions of the elements to swap in the permutation.
It is guaranteed that the sum of all $n$ does not exceed $65\,535$, and the sum of all $q$ does not exceed $5 \cdot 10^4$.
Output
For each test case, print $q$ lines corresponding to the $q$ queries. For each query, output $\texttt{YES}$ if there is a DFS order that exactly equals the current permutation, and output $\texttt{NO}$ otherwise.
You can output $\texttt{Yes}$ and $\texttt{No}$ in any case (for example, strings $\texttt{yEs}$, $\texttt{yes}$, $\texttt{Yes}$ and $\texttt{YES}$ will be recognized as a positive response).
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
Note
In the first test case, the permutation $p_1, p_2, \ldots, p_n$ after each modification is $[1,3,2],[1,2,3],[3,2,1]$, respectively. The first two permutations are valid DFS orders; the third is not a DFS order.
In the second test case, the permutation $p_1, p_2, \ldots, p_n$ after each modification is $[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]$, respectively.