Это лёгкая версия задачи. В этой версии заданное дерево является полным бинарным деревом, а ограничения на \(n\) и \(q\) ниже. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Вам дано полное бинарное дерево\(^\dagger\), состоящее из \(n\) вершин. Вершины пронумерованы от \(1\) до \(n\), вершина \(1\) — корень. Вам также дана перестановка \(p_1, p_2, \ldots, p_n\) чисел \([1,2,\ldots,n]\).
Вам нужно ответить на \(q\) запросов. В каждом запросе вам даются два целых числа \(x\), \(y\); вам нужно поменять местами \(p_x\) и \(p_y\) и определить, является ли \(p_1, p_2, \ldots, p_n\) возможным порядком обхода в глубину\(^\ddagger\) заданного дерева.
Обратите внимание, что перестановки элементов сохраняются между запросами.
\(^\dagger\) Полное бинарное дерево — это дерево с корнем в вершине \(1\), имеющее размер \(n=2^k-1\) для некоторого целого положительного числа \(k\), и где родитель каждой вершины \(i\) (\(1<i\le n\)) — это \(\left\lfloor\frac{i}{2}\right\rfloor\). Таким образом, все листья этого дерева находятся на расстоянии \(k - 1\) от корня.
\(^\ddagger\) Порядок обхода в глубину получается вызовом следующей функции \(\texttt{dfs}\) на заданном дереве.
dfs_order = []
function dfs(v):
добавить v в конец dfs_order
выбрать произвольную перестановку s детей v
for child in s:
dfs(child)
dfs(1)
Обратите внимание, что порядок обхода DFS определён не однозначно.
Выходные данные
Для каждого набора входных данных выведите \(q\) строк, соответствующих \(q\) запросам. Для каждого запроса выведите \(\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]\) соответственно. Первые две перестановки — это возможные порядки обхода в глубину; третья — не порядок обхода в глубину.
Во втором наборе входных данных перестановка \(p_1, p_2, \ldots, p_n\) после каждой модификации равна \([1,2,3,4,5,6,7],[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]\) соответственно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|