class UFNode;
class LNode {
public:
    UFNode *Myval;
    LNode *Prev, *Next;
    LNode() :Prev(NULL), Next(NULL), Myval(NULL) {}
    LNode(LNode *pr, LNode *nx, UFNode *val) :Prev(pr), Next(nx), Myval(val) {}
    void Isolate() {
        if (this->Prev) {
            this->Prev->Next = this->Next;
        }
        this->Next->Prev = this->Prev;
        this->Prev = NULL;
        this->Next = new LNode(this, NULL, NULL);
    }

    static void Isolate(LNode* st, LNode* en);
    static void Insert(LNode* lis, LNode* nod);
    static void InsertChild(LNode* lis, UFNode* np, LNode* nod);
    static void InsertNL(LNode* lis, LNode* nod);
    static void Splice(LNode* pl, LNode* st, LNode* en);
};

class UFNode {
public:
    UFNode* p;
    int rank = 0, elem, NLcou = 0, Ccou = 0;;
    LNode *NLnode, *DFSnode, *Cnode;
    LNode* Child, *Chlast, *ChNL, *ChNLlast;
    LNode *DFSlast;

    UFNode(int element) :elem(element), p(this) {
        DFSlast = new LNode;
        DFSnode = new LNode(NULL, DFSlast, this);
        NLnode = new LNode(NULL, new LNode, this);
        Cnode = new LNode(NULL, new LNode, this);

        DFSlast->Prev = DFSnode;
        Chlast = new LNode;
        Child = Chlast;
        ChNLlast = new LNode;
        ChNL = ChNLlast;
        p = this;
    }

    void Init() {
        DFSnode->Isolate();
        Cnode->Isolate();
        NLnode->Isolate();
        p = this;
        DFSnode->Prev = NULL;
        DFSnode->Next = DFSlast;
        DFSlast->Prev = DFSnode;
        ChNL = ChNLlast;
        ChNLlast->Prev = NULL;
        Cnode->Prev = NULL;
        NLnode->Prev = NULL;
        Child = Chlast;
        Chlast->Prev = NULL;
        rank = 0, NLcou = 0, Ccou = 0;
    }
};

void LNode::Isolate(LNode* st, LNode* en) {
    if (st->Prev) {
        st->Prev->Next = en->Next;
    }

    en->Next->Prev = st->Prev;
    st->Prev = NULL;
    en->Next = new LNode(en, NULL, NULL);
}
void LNode::Insert(LNode* lis, LNode* nod) {
    nod->Isolate();
    delete nod->Next;

    nod->Prev = lis->Prev;
    nod->Next = lis;
    if (lis->Prev)
        lis->Prev->Next = nod;
    lis->Prev = nod;
}
void LNode::InsertChild(LNode* lis, UFNode* np, LNode* nod) {
    if (nod->Myval != nod->Myval->p && !nod->Prev)
        nod->Myval->p->Child = nod->Next;
    Insert(lis, nod);
    if (!nod->Prev)
        np->Child = nod;
    if (nod->Myval != nod->Myval->p)
        nod->Myval->p->Ccou--;
    np->Ccou++;
    nod->Myval->p = np;
}
void LNode::Splice(LNode* pl, LNode* st, LNode* en) {
    Isolate(st, en);
    delete en->Next;
    en->Next = pl;
    st->Prev = pl->Prev;
    if (pl->Prev)
        pl->Prev->Next = st;
    pl->Prev = en;
}

class UnionFind_Deletion {
public:
    int n, setcou = 0;
    vector<UFNode*> element;

    UnionFind_Deletion(int size) : n(size), element(n, NULL) {
        REP(i, n) {
            element[i] = new UFNode(i);
        }
    }
    bool isReduced(UFNode* root) {
        return !root->NLcou;
    }
    bool isRoot(UFNode* node) {
        return node->p == node;
    }

    void Unite(int a, int b) {// O(A(n))
        UFNode *ap = Find(a),
            *bp = Find(b);
        if (ap == bp)return;
        if (ap->rank < bp->rank) swap(ap, bp);
        else if (ap->rank == bp->rank && ap->Ccou < bp->Ccou) swap(ap, bp);

        if (isReduced(bp) && bp->Ccou < 4) {

            while (bp->Child->Myval != NULL) {
                bp->Child->Myval->rank = 0;
                LNode* buf = bp->Child->Next;
                LNode::Insert(ap->DFSnode->Next, bp->Child->Myval->DFSnode);
                LNode::InsertChild(ap->Child, ap, bp->Child);
            }

            bp->rank = 0;
            LNode::InsertChild(ap->Child, ap, bp->Cnode);
            LNode::Insert(ap->DFSnode->Next, bp->DFSnode);
            ap->rank = max(ap->rank, 1);
        }
        else {
            if (ap->rank == bp->rank)
                ap->rank++;
            LNode::InsertChild(ap->Child, ap, bp->Cnode);
            LNode::Insert(ap->ChNL, bp->NLnode);
            ap->ChNL = bp->NLnode;
            ap->NLcou++;


            LNode::Splice(ap->DFSnode->Next, bp->DFSnode, bp->DFSlast->Prev);
        }
    }

    UFNode* Relink(UFNode* a, bool LRB = 0) {
        UFNode *par = a->p;
        if (isRoot(par)) return a;
        if (par->Chlast->Prev && par->Chlast->Prev->Myval != a) {
            LNode::InsertChild(par->Cnode, par->p, a->Cnode);
            LNode::Splice(par->DFSnode->Next, a->DFSnode, a->Cnode->Next->Myval->DFSnode->Prev);
        }
        else {
            LNode::InsertChild(par->Cnode->Next, par->p, a->Cnode);
        }

        if (!par->Ccou) {
            par->rank = 0;
            if (isRoot(par->p)) {
                if (par->p->ChNL == par->NLnode)
                    par->p->ChNL = par->NLnode->Next;
                par->NLnode->Isolate();
                par->p->NLcou--;
                if (!par->p->NLcou)
                    par->p->rank = 1;
            }

        }
        if (!LRB && (par->Ccou > 0 && par->Ccou < 3)) {
            Relink(par->Child->Myval);
        }
        return a;
    }

    UFNode* Find(int a) {// O(A(n))
        UFNode* x = element[a];
        while (!isRoot(x->p)) {
            UFNode* t = x->p;
            Relink(x);
            x = t;
        }
        return x->p;
    }

    void Delete(int a) {// O(1)
        UFNode* x = element[a];
        UFNode *leaf = x, *par;

        if (x->Ccou) {
            if (isRoot(x) && isReduced(x)) {
                leaf = x->Child->Myval;
            }
            else {
                if (isRoot(x))
                    leaf = x->DFSlast->Prev->Myval;
                else {
                    if (x->Cnode->Next->Myval)
                        leaf = x->Cnode->Next->Myval->DFSnode->Prev->Myval;
                    else
                        leaf = x->DFSnode->Prev->Myval;
                }
            }
        }
        swap(element[x->elem], element[leaf->elem]);
        swap(x->elem, leaf->elem);

        par = leaf->p;
        par->Ccou--;
        if (leaf->Cnode->Prev == NULL)
            par->Child = leaf->Cnode->Next;

        leaf->Init();

        if (!(isRoot(par) && isReduced(par))) {
            if (par->Ccou < 3)
                if (isRoot(par)) {
                    UFNode* nl = par->NLnode->Myval;

                    Relink(nl->Child->Next->Next->Myval, 1);
                    Relink(nl->Child->Next->Myval, 1);
                    Relink(nl->Child->Myval);
                }
                else {
                    Relink(par->Child->Next->Myval, 1);
                    Relink(par->Child->Myval);
                }
        }
        if (isRoot(par) && isReduced(par))
            par->rank = 1;
    }


};