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 \lt 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.

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 \lt 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).

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.

#	Name	Rating↕	Solved↕
2002D1	DFS Checker (Easy Version) brute force data structures dfs and similar graphs hashing trees	1900	5.2k
1996G	Penacony brute force data structures graphs greedy hashing	2200	2.4k
1574D	The Strongest Build binary search brute force data structures dfs and similar graphs greedy hashing implementation	2000	4.9k

Problemset