因为只能支持加入一个边维护边双，所以时光倒流

维护好边双，每次就是提取出(x,y)的链，答案就是链长度-1

具体维护边双的话，

void access(int x){    for(reg y=0;x;y=x,x=t[y].fa=fin(t[x].fa)){//注意更新 splay(x);rs=y;pushup(x); } }

dele(int x,int y)把x节点的father指向y，这个x临死前把信息指到y，以便于后面要找x的直接找y即可。{

　　if(x) fa[x]=y,dele(rs,y),dele(ls,y)

}

merge函数(int x,int y){

　　if(x==y（在一起）)return 什么都不用做

　　makert(x)

　　if(findrt(y)!=x){

　　　　t[x].fa=y相当于直接link

　　　　return;

　　}

　　splay(x)

　　出环了。那么要缩点，x现在是根，并且作为代表点

　　dele(rs,x)

　　t[x].ch[1]=0,干掉子树，这个子树已经名存实亡了。

　　pushup(x)

}

我通过merge，dele函数打上标记，

在access的时候把标记依次还原，达到真正缩点的目的。

而并查集使我每次都会到真正的节点。不会到已经删除的节点。

 

代码：

#include
     
      #define il inline#define reg register int#define numb (ch^'0')#define ls t[x].ch[0]#define rs t[x].ch[1]using namespace std;typedef long long ll;il void rd(int &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=30000+5;const int M=100000+5;int n,m;struct node{    int sz,fa,ch[2],r;}t[N];int fa[N];int fin(int x){    return fa[x]==x?x:fa[x]=fin(fa[x]);}bool nrt(int x){    return (t[t[x].fa].ch[0]==x)||(t[t[x].fa].ch[1]==x);}void rev(int x){    swap(t[x].ch[0],t[x].ch[1]);    t[x].r^=1;    }void pushdown(int x){    if(t[x].r){        t[x].r=0;        rev(ls);rev(rs);    }}void pushup(int x){    t[x].sz=t[ls].sz+t[rs].sz+1;}void rotate(int x){    int y=t[x].fa,d=t[y].ch[1]==x;    t[t[y].ch[d]=t[x].ch[!d]].fa=y;    if(nrt(y)) t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[1]==y]=x;    else t[x].fa=t[y].fa;    t[t[y].fa=x].ch[!d]=y;    pushup(y);}int sta[N];void splay(int x){    int y=x,z=0;    sta[++z]=y;    while(nrt(y)) y=t[y].fa,sta[++z]=y;    while(z) pushdown(sta[z--]);        while(nrt(x)){        y=t[x].fa,z=t[y].fa;        if(nrt(y)){            rotate(((t[y].ch[0]==x)==(t[z].ch[0]==y))?y:x);                    }        rotate(x);    }    pushup(x);}void access(int x){    for(reg y=0;x;y=x,x=t[y].fa=fin(t[x].fa)){        splay(x);rs=y;pushup(x);    }}void makert(int x){    access(x);splay(x);rev(x);}int findrt(int x){    access(x);splay(x);    pushdown(x);    while(t[x].ch[0]) pushdown(x=t[x].ch[0]);    splay(x);    return x;}void dele(int x,int y){    if(x) fa[x]=y,dele(ls,y),dele(rs,y);}void merge(int x,int y){    if(x==y) return;    makert(x);    if(findrt(y)!=x){        t[x].fa=y;        pushup(y);        return;    }    dele(t[x].ch[1],x);    t[x].ch[1]=0;    pushup(x);}void split(int x,int y){    makert(x);access(y);splay(y);}struct edge{    int x,y;    bool friend operator <(edge a,edge b){        if(a.x==b.x) return a.y
      
       y) swap(x,y);        e[i].x=x;e[i].y=y;    }    sort(e+1,e+m+1);    int c;    int tot=0;    while(1){        rd(c);        if(c==-1) break;        ++tot;        rd(x);rd(y);        if(x>y) swap(x,y);        if(c==0){            edge lp;lp.x=x,lp.y=y;            vis[lower_bound(e+1,e+m+1,lp)-e]=1;        }        q[tot].x=x,q[tot].y=y;        q[tot].c=c;    }    for(reg i=1;i<=m;++i){        if(!vis[i]){            x=fin(e[i].x),y=fin(e[i].y);            merge(x,y);        }    }    for(reg i=tot;i>=1;--i){        x=fin(q[i].x);y=fin(q[i].y);        if(q[i].c==1){            ++cnt;            split(x,y);            ans[cnt]=t[y].sz-1;        }        else{            merge(x,y);        }    }    for(reg i=cnt;i>=1;--i){        printf("%d\n",ans[i]);    }    return 0;}}signed main(){    Miracle::main();    return 0;}/*   Author: *Miracle*   Date: 2018/12/19 9:57:28*/