#include <bits/stdc++.h>

 using namespace std;

 struct Link_Cut_Tree

 {

     static const int MAXN =  + ;

     int ch[MAXN][], fa[MAXN], rev[MAXN], sz[MAXN];

     int sk[MAXN];

     bool isroot(int x)

     {

         return ch[fa[x]][] != x && ch[fa[x]][] != x;

     }

     void reverse(int x)

     {

         rev[x] ^= , swap(ch[x][],ch[x][]);

     }

     void update(int x)

     {

         sz[x] = sz[ch[x][]] +  sz[ch[x][]] +;

     }

     void push_down(int x)

     {

         if(!rev[x]) return ;

         if(ch[x][]) reverse(ch[x][]);

         if(ch[x][]) reverse(ch[x][]);

         rev[x]=;

     }

     void rotate(int x)

     {

         int f = fa[x], gf = fa[f];

         int t1 = ( x != ch[f][]), t2 = ( f != ch[gf][]), tmp = ch[x][^t1];

         if(!isroot(f)) ch[gf][^t2] = x;

         fa[tmp] = f, fa[x] = gf, ch[x][^t1] = f, fa[f] = x, ch[f][^t1] = tmp;

         update(f);

     }

     void splay(int x)

     {

         int top = ;

         sk[++top] = x;

         for(int i = x; !isroot(i); i = fa[i])   sk[++top] = fa[i];

         while(top)  push_down(sk[top--]);

         for(int f = fa[x], gf = fa[f]; !isroot(x); rotate(x), f = fa[x],gf = fa[f])

         if(!isroot(f))

             rotate((x==ch[f][]) ^ (f==ch[gf][]) ? x : f);

         update(x);

     }

     void access(int x)

     {

         for(int p = ; x; p = x, x = fa[x])

             splay(x), ch[x][] = p, update(x);

     }

     void makeroot(int x)

     {

         access(x), splay(x), reverse(x);

     }

     int findroot(int x)

     {

         access(x), splay(x);

         while(ch[x][]) x = ch[x][];

         return x;

     }

     void link(int x,int y)

     {

         makeroot(x), fa[x] = y;

     }

     void cut(int x,int y)

     {

         makeroot(x), access(y), splay(y);

         if(ch[y][] == x)   ch[y][] = fa[x] = ;

         update(y);

     }

     void debug(void)

     {

         for(int i=;i<=;i++)

             printf("%d %d %d %d %d %d %d\n",i,fa[i],ch[i][],ch[i][],rev[i],sz[i]);

     }

 }lct;

 int main(void)

 {

     return ;

 }