Description
Byteasar是一个很纠结的人。每次他经过Bytetown的时候都知道有至少2条不同的路径可以选择，这导致他必须花很长时间来决定走哪条路。Byteasar最近听说了Bytetown的修路计划，他可能是唯一一个为此感到高兴的人——他有机会消除他的烦恼。
在Byteasar一共有n个岔口，连接着m条双向道路。两条路径完全不同当且仅当他们没有公共的道路（但是允许经过相同的岔口）。
Byteasar想知道：对于两个岔口x y，是否存在一对完全不同的路径。
Input
第一行3个整数：n, m, z (2<=n<=100000, 1<=m,z<=100000)，分别代表：n个岔口，m条边，事件数z。岔口编号为1~n。
下面m行：ai, bi (1<=ai,bi<= n, ai!=bi)，描述一条边
然后下面z行描述事件：ti, ci, di (t='Z' or 'P', 1<=ci,di<=n, ci!=di)。事件按照时间排序。
- 当
t='Z'，表示删除一条边(ci, di)，保证这条边之前没有被删除。注意，边可以被全部删除！ - 当
t='P'，询问是否存在从ci到di的一对完全不同的路径。
Output
对于每组询问，如果存在，输出TAK，否则输出NIE。
逆着操作顺序加边，同时并查集维护连通性和边双连通分量
预处理出按加边顺序得到的生成森林，在上面把每个连通块定向为有根树并标上深度
正式加边时，若两侧不连通则标为联通，否则将边的两端在生成树上的路径并成同一个边双连通分量
查询时可以直接判断两点是否在同个边双连通分量内
#include<bits/stdc++.h> char buf[5000000],*ptr=buf-1; int _(){ int x=0,c=*++ptr; while(c<48)c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x; } int _o(){ int c=*++ptr; while(c<'A'||c>'Z')c=*++ptr; return c; } const int N=100007; int es[N*2],enx[N*2],ev[N*2],e0[N],ep=2,del[N]; int n,m,q,qs[N][3],f1[N],f2[N],fa[N],ap=0,dep[N]; bool ed[N],as[N]; int get(int*f,int x){ int a=x,c; while(x!=f[x])x=f[x]; while(x!=f[a])c=f[a],f[a]=x,a=c; return x; } struct edge{ int a,b,id; bool operator<(edge e)const{return a!=e.a?a<e.a:b<e.b;} void chk(){ int x=get(f1,a),y=get(f1,b); if(x!=y){ f1[x]=y; ev[id<<1]=ev[id<<1|1]=1; } } void ins(){ int x=get(f1,a),y=get(f1,b); if(x!=y){ f1[x]=y; return; } a=get(f2,a);b=get(f2,b); while(a!=b){ if(dep[a]<dep[b])b=f2[b]=get(f2,fa[b]); else a=f2[a]=get(f2,fa[a]); } } }e[N]; void dfs(int w){ ed[w]=1; for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(!ed[u]&&ev[i])fa[u]=w,dep[u]=dep[w]+1,dfs(u); } } void ae(){ int a=_(),b=_(); if(a>b)std::swap(a,b); e[ep>>1]=(edge){a,b,ep>>1}; es[ep]=b;enx[ep]=e0[a];e0[a]=ep++; es[ep]=a;enx[ep]=e0[b];e0[b]=ep++; } void query(int a,int b){ as[ap++]=(get(f2,a)==get(f2,b)); } int main(){ fread(buf,1,sizeof(buf),stdin); n=_();m=_();q=_(); for(int i=1;i<=m;++i)ae(); std::sort(e+1,e+m+1); for(int i=1,a,b;i<=q;++i){ if(qs[i][0]=(_o()=='Z')){ a=_();b=_(); if(a>b)std::swap(a,b); a=std::lower_bound(e+1,e+m+1,(edge){a,b})-e; ++del[a]; qs[i][1]=a; }else{ qs[i][1]=_(); qs[i][2]=_(); } } for(int i=1;i<=n;++i)f1[i]=i; for(int i=1;i<=m;++i){ while(del[i])i+=del[i]; if(i<=m)e[i].chk(); } for(int i=q;i;--i)if(qs[i][0])e[qs[i][1]].chk(); for(int i=1;i<=n;++i)if(!ed[i])dfs(i); for(int i=1;i<=n;++i)f1[i]=f2[i]=i; for(int i=1;i<=m;++i){ while(del[i])i+=del[i]; if(i<=m)e[i].ins(); } for(int i=q;i;--i)if(qs[i][0])e[qs[i][1]].ins();else query(qs[i][1],qs[i][2]); while(ap)puts(as[--ap]?"TAK":"NIE"); return 0; }