洛谷题目传送门

太弱了不会树剖，觉得LCT好写一些，就上LCT乱搞，当LCT维护双连通分量的练手题好了

正序删边是不好来维护连通性的，于是就像水管局长那样离线处理，逆序完成操作

显然，每个点可以代表一个双连通分量，查询就是链的长度-1

连接一条边，如果在LCT中还没连通就link，如果连通了，显然这里会出现一个环，然后暴力缩点，可以把当前辅助树的根节点当做集合的标志节点，然后dfs整个辅助树，把链上的其它点的并查集祖先暴力改成这个标志节点，最后再断开标志节点与子树的连接。总的暴力修改次数不会超过\(N\log N\)次，复杂度是对的

但是点缩完了，那它们的子树不会指空吗？所以，access的时候，要更新\(x\)为\(geth(f[x])\)

至于常数，LCT也并不是很慢啊。反正有了O2还是可以做到很优秀的

代码细节很多，调试真心累TAT

#include<cstdio>

#include<algorithm>

using namespace std;

#define RG register

#define R RG short

#define I inline void

#define IB inline bool

#define IS inline short

#define G ch=getchar()

#define lc c[x][0]

#define rc c[x][1]

const int N=30009,M=100009;

short f[N],c[N][2],s[N],h[N],a[N],b[N],op[N],ans[M];

bool r[N],vis[M];

struct EDGE{//对边排序，方便查找该边是否被删除

    short x,y;

    IB operator<(const EDGE a)const{

        return x<a.x||(x==a.x&&y<a.y);

    }

}e[M];

template<typename T>

I in(RG T&z){

    RG char G;

    while(ch<'-')G;

    z=ch&15;G;

    while(ch>'-')z*=10,z+=ch&15,G;

}

IS geth(R x){

    if(x==h[x])return x;

    return h[x]=geth(h[x]);

}

IB nroot(R x){

    return c[f[x]][0]==x||c[f[x]][1]==x;

}

I pushup(R x){

    s[x]=s[lc]+s[rc]+1;

}

I pushdown(R x){

    if(r[x]){

        swap(lc,rc);

        r[lc]^=1;r[rc]^=1;r[x]=0;

    }

}

I pushall(R x){

    if(nroot(x))pushall(f[x]);

    pushdown(x);

}

I rotate(R x){

    R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];

    if(nroot(y))c[z][c[z][1]==y]=x;f[x]=z;

    c[x][!k]=y;f[y]=x;

    c[y][k]=w;f[w]=y;

    pushup(y);

}

I splay(R x){

    pushall(x);

    R y;

    while(nroot(x)){

        if(nroot(y=f[x]))

            rotate((c[f[y]][0]==y)^(c[y][0]==x)?x:y);

        rotate(x);

    }

    pushup(x);

}

I access(R x){

    for(R y=0;x;y=x,x=f[y]=geth(f[x]))//注意更新

        splay(x),rc=y,pushup(x);

}

I makeroot(R x){

    access(x);splay(x);

    r[x]^=1;

}

IS findroot(R x){

    access(x);splay(x);

    pushdown(x);

    while(lc)pushdown(x=lc);

    splay(x);

    return x;

}

I split(R x,R y){

    makeroot(y);

    access(x);splay(x);

}

I del(R x,R y){//函数递归缩点

    if(x)h[x]=y,del(lc,y),del(rc,y);

}

I merge(R x,R y){

    if(x==y)return;//在一个分量里什么都不用干

    makeroot(x);

    if(findroot(y)!=x){

        f[x]=y;return;//等于link

    }

    del(rc,x);

    rc=0;pushup(x);//缩点，删点

}

int main(){

    RG int n,m,i,j;

    R x,y;

    in(n);in(m);

    for(i=1;i<=n;++i)s[i]=1,h[i]=i;

    for(i=1;i<=m;++i){

        in(x);in(y);

        if(x>y)swap(x,y);//强制编号，方便以后查找

        e[i]=(EDGE){x,y};

    }

    sort(e+1,e+m+1);

    for(j=1;in(op[j]),op[j]!=131;++j){

        in(x);in(y);

        if(!op[j]){

            if(x>y)swap(x,y);

            vis[lower_bound(e+1,e+m+1,(EDGE){x,y})-e]=1;

        }//重载完小于号，直接二分找到，再打上删除记号

        a[j]=x;b[j]=y;

    }

    for(i=1;i<=m;++i)

        if(!vis[i])merge(geth(e[i].x),geth(e[i].y));

    for(i=0,--j;j;--j){

        x=geth(a[j]);y=geth(b[j]);

        if(op[j])split(x,y),ans[++i]=s[x]-1;

        else merge(x,y);

    }

    while(i)printf("%hd\n",ans[i--]);

    return 0;

}