Это сложная версия задачи. В этой версии на заданное дерево нет дополнительных ограничений, а ограничения на \(n\) и \(q\) выше. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Вам дано корневое дерево, состоящее из \(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\) возможным порядком обхода в глубину\(^\dagger\) заданного дерева.
Обратите внимание, что перестановки элементов сохраняются между запросами.
\(^\dagger\) Порядок обхода в глубину получается вызовом следующей функции \(\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
|
3
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
5 4
1 1 3 4
2 3 4 5 1
5 1
4 5
3 4
2 3
|
YES
YES
NO
YES
NO
NO
YES
YES
NO
NO
YES
|