CF2002D1.DFS Checker (Easy Version)

这是该问题的简单版本。在本版本中，给定的树是一棵完美二叉树，并且 $n$ 和 $q$ 的约束较低。只有在你同时解决了两个版本的问题后，才能进行 hack。

给定一棵包含 $n$ 个顶点的完美二叉树 $^\dagger$。顶点编号为 $1$ 到 $n$，根节点为顶点 $1$。同时给定一个 $[1,2,\ldots,n]$ 的排列 $p_1, p_2, \ldots, p_n$。

你需要回答 $q$ 个询问。每个询问给出两个整数 $x$、$y$；你需要交换 $p_x$ 和 $p_y$，并判断 $p_1, p_2, \ldots, p_n$ 是否是该树的一个合法 DFS 序 $^\ddagger$。

请注意，交换操作在所有询问中是持续生效的。

$^\dagger$ 完美二叉树是指以顶点 $1$ 为根的树，大小为 $n=2^k-1$（$k$ 为正整数），并且每个顶点 $i$（$1<i\le n$）的父节点为 $\left\lfloor\frac{i}{2}\right\rfloor$。因此，该树的所有叶子节点距离根节点的距离均为 $k-1$。

$^\ddagger$ DFS 序是通过对给定树调用如下 $\texttt{dfs}$ 函数得到的。

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)

注意，DFS 序不是唯一的。

每个测试包含多组测试用例。第一行包含测试用例数 $t$（$1\le t\le 10^4$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$、$q$（$3\le n\le 65535$，$2\le q\le 5\times 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$ 的总和不超过 $65535$，所有 $q$ 的总和不超过 $5\times 10^4$。

对于每个测试用例，输出 $q$ 行，每行对应一个询问。对于每个询问，如果当前排列存在一个合法的 DFS 序与之完全相同，则输出 $\texttt{YES}$，否则输出 $\texttt{NO}$。

你可以以任意大小写输出 $\texttt{Yes}$ 和 $\texttt{No}$（例如 $\texttt{yEs}$、$\texttt{yes}$、$\texttt{Yes}$ 和 $\texttt{YES}$ 都会被识别为肯定回答）。

在第一个测试用例中，每次修改后的排列 $p_1, p_2, \ldots, p_n$ 分别为 $[1,3,2]$、$[1,2,3]$、$[3,2,1]$。前两个排列是合法的 DFS 序，第三个不是。

在第二个测试用例中，每次修改后的排列 $p_1, p_2, \ldots, p_n$ 分别为 $[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]$。

由 ChatGPT 4.1 翻译