write a go solution for D2. DFS Checker (Hard Version)time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis 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 textttdfs 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.InputEach test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10^4). The description of the test cases follows. The first line of each test case contains two integers n, q (2<=n<=3*10^5, 2<=q<=10^5) — the number of vertices in the tree and the number of queries.The next line contains n-1 integers a_2,a_3,ldots,a_n (1<=a_i<i) — the parent of each vertex in the given tree.The next line contains n integers p_1,p_2,ldots,p_n (1<=p_i<=n, all p_i are distinct) — the initial permutation p.The next q lines each contain two integers x, y (1<=x,y<=n,xneqy) — the positions of the elements to swap in the permutation.It is guaranteed that the sum of all n does not exceed 3*10^5, and the sum of all q does not exceed 10^5.OutputFor each test case, print q lines corresponding to the q queries. For each query, output textttYES if there is a DFS order that exactly equals the current permutation, and output textttNO otherwise.You can output textttYes and textttNo in any case (for example, strings textttyEs, textttyes, textttYes, and textttYES will be recognized as a positive response).ExampleInput33 31 11 2 32 33 21 37 41 1 2 2 3 31 2 3 4 5 6 73 52 53 74 65 41 1 3 42 3 4 5 15 14 53 42 3OutputYES
YES
NO
YES
NO
NO
YES
YES
NO
NO
YES
NoteIn 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.. Output only the code with no comments, explanation, or additional text.