#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

const int N = 5e5 + ;

struct Node{

    int rev, rt;

    int son[], pre;

    int mx, val, id;

    void init(){

        rt = ; rev = pre = son[] = son[] = ;

        mx = val = id = ;

    }

}tr[N];

void Push_Rev(int x){

    if(!x) return ;

    swap(lch(x), rch(x));

    tr[x].rev ^= ;

}

void Push_Up(int x){

    if(!x) return ;

    tr[x].mx = tr[x].val, tr[x].id = x;

    if(tr[x].mx < tr[lch(x)].mx) tr[x].mx = tr[lch(x)].mx, tr[x].id = tr[lch(x)].id;

    if(tr[x].mx < tr[rch(x)].mx) tr[x].mx = tr[rch(x)].mx, tr[x].id = tr[rch(x)].id;

}

void Push_Down(int x){

   if(tr[x].rev){

        tr[x].rev = ;

        Push_Rev(lch(x));

        Push_Rev(rch(x));

    }

}

void Rev(int x){

    if(!tr[x].rt) Rev(tr[x].pre);

    Push_Down(x);

}

void rotate(int x){

    if(tr[x].rt) return;

    int y = tr[x].pre, z = tr[y].pre;

    int k = (rch(y) == x);

    tr[y].son[k] = tr[x].son[k^];

    tr[tr[y].son[k]].pre = y;

    tr[x].son[k^] = y;

    tr[y].pre = x;

    tr[x].pre = z;

    if(tr[y].rt) tr[y].rt = , tr[x].rt = ;

    else tr[z].son[rch(z) == y] = x;

    Push_Up(y);

}

void Splay(int x){

     Rev(x);

     while(!tr[x].rt){

        int y = tr[x].pre, z = tr[y].pre;

        if(!tr[y].rt){

            if(( x == rch(y) ) != (y == rch(z))) rotate(x);

            else rotate(y);

        }

        rotate(x);

    }

    Push_Up(x);

}

void Access(int x){

    int y = ;

    do{

        Splay(x);

        tr[rch(x)].rt = ;

        rch(x) = y;

        tr[y].rt = ;

        Push_Up(x);

        y = x;

        x = tr[x].pre;

    }while(x);

}

void Make_rt(int x){

    Access(x);

    Splay(x);

    Push_Rev(x);

}

bool judge(int u, int v){

    while(tr[u].pre) u = tr[u].pre;

    while(tr[v].pre) v = tr[v].pre;

    return u == v;

}

void link(int u, int v){

    Make_rt(u);

    tr[u].pre = v;

}

void cut(int u, int v){

    Make_rt(u);

    Access(v);

    Splay(v);

    tr[lch(v)].pre = ;

    tr[lch(v)].rt = ;

    tr[v].pre = ;

    lch(v) = ;

}

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

const int N = 5e5 + ;

struct Node{

    int rev, rt;

    int son[], pre;

    int sum, vsum, key;

    void init(){

        rt = ; rev = pre = son[] = son[] = ;

        sum = vsum = key = ;

    }

}tr[N];

void Push_Rev(int x){

    if(!x) return ;

    swap(lch(x), rch(x));

    tr[x].rev ^= ;

}

void Push_Up(int x){

    if(!x) return ;

    tr[x].sum = tr[x].key ^ tr[lch(x)].sum ^ tr[rch(x)].sum ^ tr[x].vsum;

}

void Push_Down(int x){

   if(tr[x].rev){

        tr[x].rev = ;

        Push_Rev(lch(x));

        Push_Rev(rch(x));

    }

}

void Rev(int x){

    if(!tr[x].rt) Rev(tr[x].pre);

    Push_Down(x);

}

void rotate(int x){

    if(tr[x].rt) return;

    int y = tr[x].pre, z = tr[y].pre;

    int k = (rch(y) == x);

    tr[y].son[k] = tr[x].son[k^];

    tr[tr[y].son[k]].pre = y;

    tr[x].son[k^] = y;

    tr[y].pre = x;

    tr[x].pre = z;

    if(tr[y].rt) tr[y].rt = , tr[x].rt = ;

    else tr[z].son[rch(z) == y] = x;

    Push_Up(y);

}

void Splay(int x){

     Rev(x);

     while(!tr[x].rt){

        int y = tr[x].pre, z = tr[y].pre;

        if(!tr[y].rt){

            if(( x == rch(y) ) != (y == rch(z))) rotate(x);

            else rotate(y);

        }

        rotate(x);

    }

    Push_Up(x);

}

void Access(int x){

    int y = ;

    do{

        Splay(x);

        tr[rch(x)].rt = ;

        tr[x].vsum ^= tr[rch(x)].sum;

        rch(x) = y;

        tr[x].vsum ^= tr[rch(x)].sum;

        tr[y].rt = ;

        Push_Up(x);

        y = x;

        x = tr[x].pre;

    }while(x);

}

void Make_rt(int x){

    Access(x);

    Splay(x);

    Push_Rev(x);

}

void link(int u, int v){

    Make_rt(u);

    Access(v);

    Splay(v);

    tr[u].pre = v;

    tr[v].

    vsum ^= tr[u].sum;

    Push_Up(v);

}

void cut(int u, int v){

    Make_rt(u);

    Access(v);

    Splay(v);

    tr[lch(v)].pre = ;

    tr[lch(v)].rt = ;

    tr[v].pre = ;

    lch(v) = ;

    Push_Up(v);

}