CF2002D1 DFS Checker (Easy Version)

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

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

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

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.