Let us first fix some \(v\). Then the problem is boiled down to as follows:

Given integer sequences $A$ and $B$, each of length $N$, choose either $A_i$ or $B_i$ for each $i(1 \le i \le N)$ to maximize the number of distinct integers chosen.

This problem is solved by preparing an \(N\)-vertex graph, where \(A_i\) and \(B_i\) are connected with an edge for \(1 \le i \le N\). Then, the answer is the sum of \(\min(\)number of edges, number of vertices\()\) over all connected components.

However, performing this for every vertex \(v\) requires an \(\mathrm{O}(N^2)\) time, which exceeds the time limit. Here, we optimize it using DSU (Disjoint Set Union).

Perform a DFS (Depth First Search) from vertex \(1\) while adding and removing an edge between \(A_i\) and \(B_i\). Here, since it is DFS, the edge to be removed is always the last edge added. Thus, it is sufficient to recover the state of DSU before the last update.

In addition to the data ordinarily stored in a DSU, we also store the number of edges in the connected component and the sum of \(\min(\)number of edges, number of vertices\()\) for each connected component. To support edge removals, we maintain what was updated by the \(i\)-th query, as well as the original value.

For an edge addition query, we merge the smaller connected component into the larger, as in an ordinary DSU. Here, the entire updated data needs to be stored. We also update \(\min(\)number of edges, number of vertices\()\) here. The complexity is \(\mathrm{O}(\log N)\), since we do not do path decompression.

For a edge deletion query, it is sufficient to revert the last update. Since a constant number of elements need to be restored, this query can be processed in a constant time.

Therefore, the problem can be solved in a total of \(\mathrm{O}(N\log N)\) time.