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

每个测试包含多组测试用例。第一行包含测试用例数 $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

对于每个测试用例，输出 $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 翻译