What is the maximum possible $$$MEX$$$? find an upper bound for the final $$$MEX$$$.

Since size of $$$c$$$ is $$$n$$$. The $$$MEX$$$ of $$$c$$$ can be at most $$$n$$$ (why?). Hence each index $$$i$$$ $$$(1 \le i \le n)$$$, can be categorized into one of three categories:

• ($$$a_i \ge n$$$ and $$$b_i \ge n$$$): such indices can be ignored as the choice here doesn't matter, neither will contribute to the $$$MEX$$$

• ($$$a_i \ge n$$$ and $$$b_i \lt n$$$) or ($$$b_i \ge n$$$ and $$$a_i \lt n$$$): when exactly one of $$$a_i$$$ and $$$b_i$$$ is less than $$$n$$$, the choice is obvious, set $$$c_i$$$ to the element less than $$$n$$$

• ($$$a_i \lt n$$$ and $$$b_i \lt n$$$): this is the non-trivial case. Try working out the example test cases manually. What do you observe?

Work through the following example:

Its quite trivial to see that for $$$c = [0, 1, 2, 3]$$$, the $$$MEX = 4$$$ is maximum possible $$$MEX$$$. One way to deconstruct this answer is to create a graph with $$$n$$$ nodes labelled $$$0, 1, ... 4$$$. Now for each index $$$i$$$ ($$$1 \le i \le n$$$), create an edge between nodes labelled $$$a_i$$$ and $$$b_i$$$. In this case the final graph would look like this:

In this case the resulting graph is a tree. From this graph we can choose all but one node to include in the array $$$c$$$, its trivial to see that the optimal element to exclude would be the maximum number which in this case is $$$4$$$. Try generalizing this logic for a tree with any $$$n$$$ nodes. What about a graph of $$$n$$$ nodes that isn't a tree?

Consider the following example:

On creating a graph in the same manner we get:

since the graph has a "loop", this isn't a tree anymore and we can include all elements of the graph in $$$c$$$. Hence the maximum $$$MEX$$$ will be $$$4$$$. One possible construction is $$$c = [1, 2, 3, 0]$$$.

We'll only be working with the non-trivial indices as discussed in Hint 2. Set up a graph initially with $$$n$$$ nodes labelled $$$0,1,...n-1$$$. For each index $$$i$$$ ($$$1 \le i \le n$$$) that is non-trivial, create an edge between nodes $$$a_i$$$ and $$$b_i$$$. We'll end up with several disjoint graph components, some that are trees and some that aren't. For each node we'll keep track of the following properties:

• an index $$$root$$$ keeping track of the root node of the disjoint graph it's present in.

• an integer $$$M$$$ keeping track of the maximum value present in it's disjoint graph.

• a boolean $$$looped$$$ that is set to $$$true$$$ when a "loop" is present in it's disjoint group, $$$false$$$ otherwise.

Keep in mind that edges can start and end at the same node to create a "loop" of one element. this can happen when $$$a_i = b_i \lt n$$$.

Initially (before creating the edges), for each index $$$i$$$ ($$$1 \le i \le n$$$) set:

• $$$root_i = i$$$ since there are no edges, there are $$$n$$$ disjoint graphs initially each with one node, which itself is the root node.

• $$$M_i = i$$$ since only one element is present in each disjoint graph, it itself is the maximum value.

• $$$looped_i = false$$$ since there are no edges, it is a tree with one node.

When creating an edge, we'll either be combining two disjoint graphs into one, or create a "loop" inside a disjoint graph if it isn't already present. To update the edges, we'll iterate through all non-trivial indices $$$i$$$ ($$$1 \le i \le n$$$). For each index $$$i$$$ we'll perform the following operations in order:

• set $$$root_{a_i} = root_{b_i}$$$. When we keep doing this, for any node $$$j$$$ which is a root node, we have $$$root_j = j$$$.

• It will be redundant to update the value of $$$M$$$ and $$$looped$$$ for all the nodes in the graph as it would be lead of a time complexity of $$$\mathcal{O}(n^2)$$$. Instead we'll just update the value of $$$M_{root_{b_i}}$$$ and $$$looped_{root_{b_i}}$$$, and when we require $$$M_j$$$ for any index $$$j$$$, we'll just find $$$root_j$$$, and update $$$M_j$$$ = $$$M_{root_j}$$$. We can do the same for $$$looped_j$$$. This would lead to a time complexity of $$$\mathcal{O}(n\cdot\alpha (n))$$$

• set $$$M_{root_{b_i}} = max(M_{root_{b_i}}, M_{root_{a_i}})$$$

• set $$$looped_{root_{b_i}} = (looped_{root_{b_i}} \ | \ looped_{root_{a_i}} \ | \ (root_{a_i} == root_{b_i}))$$$

After creating all edges, we'll have several disjoint graphs. We'll iterate from $$$i = 0$$$ to $$$i = n$$$, to check the first element $$$j$$$ that cannot be included in $$$c$$$ after optimally choosing elements from each disjoint graph. This will be our final answer. For each index $$$i$$$, either one of the following two conditions must hold if it can be included in $$$c$$$. This can be done in $$$\mathcal{O}(n)$$$

• $$$M_i \neq i$$$

• $$$looped_i = true$$$

The time complexity of our solution is $$$\mathcal{O}(n\cdot\alpha (n))$$$ where $$$\alpha$$$ is the inverse ackermann function and for all practical purposes $$$\alpha (n) \le 4$$$, which reduces our final time complexity to $$$\mathcal{O}(n)$$$ .

A bug free implementation of the above logic is given below

#include<bits/stdc++.h>
#include<vector>
using namespace std;
struct DSU{
    vector<int> parent;
    vector<int> M;
    vector<bool> looped;
    DSU(int n){
        parent.resize(n);
        M.resize(n);
        looped.assign(n, false);
        for(int i = 0; i < n; i++){
            parent[i] = i;
            M[i] = i;
        }
    }

    int find(int i){
        if(parent[i] == i){return i;}
        parent[i] = find(parent[i]);
        return parent[i];
    }

    void merge(int i, int j){
        int ri = find(i);
        int rj = find(j);
        if(ri == rj){looped[rj] = true;}
        else{         
            parent[ri] = rj;
            M[rj] = max(M[rj], M[ri]);
            looped[rj] = looped[rj] | looped[ri];
        }
    }
};
void solve()
{
    int n; cin >> n;
    vector<int> a(n); for(int i = 0; i < n; i++){cin >> a[i];}
    vector<int> b(n); for(int i = 0; i < n; i++){cin >> b[i];}
    DSU dsu(n);
    for(int i = 0; i < n; i++){
        if(a[i] >= n && b[i] >= n){continue;}
        else if(a[i] >= n){dsu.merge(b[i], b[i]);}
        else if(b[i] >= n){dsu.merge(a[i], a[i]);}
        else{dsu.merge(a[i], b[i]);}
    }
    int mex = 0;
    for(; mex < n; mex++){
        int parent = dsu.find(mex);
        if(dsu.M[parent] > mex){continue;}
        else{
            if(dsu.looped[parent]){continue;}
            else{break;}
        }
    }
    cout << mex << "\n";
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);    
    //int t = 1;
    int t; cin >> t;
    for(int i = 0; i < t; i++) {solve();}
    return 0;
}