CF2002D2 DFS Checker (Hard Version)

This is the hard version of the problem. In this version, you are given a generic tree and the constraints on $ n $ and $ q $ are higher. You can make hacks only if both versions of the problem are solved. You are given a rooted tree 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 $ ^\dagger $ of the given tree. Please note that the swaps are persistent through queries. $ ^\dagger $ A DFS order is found by calling the following $ \texttt{dfs} $ function on the given tree. ```

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


```
```

Note that the DFS order is not unique.
                            

N/A

N/A

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.