Code:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;void setIO(string a){    freopen((a+".in").c_str(),"r",stdin);}#define maxn 300080int n,m;struct Link_Cut_Tree{    int ch[maxn][2],f[maxn];    int tag[maxn],sta[maxn];    int get(int x)    {        return ch[f[x]][1]==x;    }    int which(int x)    {        return ch[f[x]][1]==x;    }    int isRoot(int x)    {        return !(ch[f[x]][1]==x||ch[f[x]][0]==x);    }    int lson(int x)    {        return ch[x][0];    }    int rson(int x)    {        return ch[x][1];    }    void mark(int x)    {        if(!x) return;        swap(ch[x][0],ch[x][1]), tag[x]^=1;    }    void pushdown(int x)    {        if(tag[x]) mark(lson(x)), mark(rson(x)),tag[x]=0;    }    void rotate(int x)    {        int old=f[x],fold=f[old],which=get(x);        if(!isRoot(old)) ch[fold][ch[fold][1]==old]=x;        ch[old][which]=ch[x][which^1],f[ch[old][which]]=old;        ch[x][which^1]=old,f[old]=x,f[x]=fold;    }    void splay(int x)    {        int v=0,u=x;        sta[++v]=u;        while(!isRoot(u)) sta[++v]=f[u],u=f[u];        while(v) pushdown(sta[v--]);        u=f[u];        for(int fa;(fa=f[x])!=u;rotate(x))            if(f[fa]!=u) rotate(get(fa)==get(x)?fa:x);    }    void Access(int x)    {        for(int y=0;x;y=x,x=f[x])            splay(x),ch[x][1]=y;    }    void makeRoot(int x)    {        Access(x), splay(x), mark(x);    }    void link(int a,int b)    {        makeRoot(a), f[a]=b;    }    int findRoot(int a)    {        Access(a),splay(a);        while(ch[a][0]) a=ch[a][0];        return a;    }    void cut(int a,int b)    {        makeRoot(a),Access(b),splay(b);        f[a]=ch[b][0]=0;    }    bool judge(int a,int b)    {        int x=findRoot(a),y=findRoot(b);        if(x!=y)return true;        return false;    }}tree;int u[maxn],v[maxn],p;int main(){    //setIO("input");    scanf("%d%d",&n,&m);    for(int i=1;i