显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
using namespace std;
inline int read(){
int sum(0),f(1);char ch(getchar());
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
return sum*f;
}
struct edge{
int s,e;
edge *n;
}*pre[30005],tmp[200005];
int tot,num;
inline void insert(int s,int e){
edge *tmp(new edge);tmp->e=e;tmp->n=pre[s];pre[s]=tmp;
}
struct node{
int op,x,y,id;
}a[40005];
int ans[40005],anstop;
int n,m,cnt;
set<pair<int,int> >ma;
int s[100005],e[100005];
int f[40005];
inline int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
int fa[40005],son[40005],size[40005],dep[40005];
inline void dfs1(int u){
size[u]=1;son[u]=0;
for(edge *i=pre[u];i;i=i->n){
int e(i->e);
if(e==fa[u])continue;
dep[e]=dep[u]+1;
fa[e]=u;
dfs1(e);
size[u]+=size[e];
if(size[e]>size[son[u]])son[u]=e;
}
}
int timee;
int top[40005],id[40005],pos[40005];
inline void dfs2(int u,int rt){
top[u]=rt;id[u]=++timee;pos[timee]=u;
if(son[u])dfs2(son[u],rt);
for(edge *i=pre[u];i;i=i->n){
int e(i->e);
if(e==fa[u]||e==son[u])continue;
dfs2(e,e);
}
}
int sum[200005],add[200005];
inline void pushup(int i){
sum[i]=sum[i<<1]+sum[i<<1|1];
}
inline void pushdown(int i,int len){
if(add[i]!=-1){
add[i<<1]=add[i<<1|1]=add[i];
sum[i<<1]=add[i]*(len-(len>>1));
sum[i<<1|1]=add[i]*(len>>1);
add[i]=-1;
}
}
inline void build(int l,int r,int i){
add[i]=-1;
if(l==r){if(l!=1)sum[i]=1;return;}
int mid((l+r)>>1);
build(l,mid,i<<1);build(mid+1,r,i<<1|1);pushup(i);
}
inline void update(int ll,int rr,int w,int l,int r,int i){
if(ll<=l&&r<=rr){sum[i]=w*(r-l+1);add[i]=w;return;}
pushdown(i,r-l+1);int mid((l+r)>>1);
if(ll<=mid)update(ll,rr,w,l,mid,i<<1);
if(mid<rr)update(ll,rr,w,mid+1,r,i<<1|1);
pushup(i);
}
inline int query(int ll,int rr,int l,int r,int i){
if(ll<=l&&r<=rr)return sum[i];
pushdown(i,r-l+1);int mid((l+r)>>1),ret(0);
if(ll<=mid)ret+=query(ll,rr,l,mid,i<<1);
if(mid<rr)ret+=query(ll,rr,mid+1,r,i<<1|1);
return ret;
}
bool used[100005];
inline void del(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(id[top[x]],id[x],0,1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(x^y)update(id[x]+1,id[y],0,1,n,1);
}
inline int ask(int x,int y){
int ret(0);
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ret+=query(id[top[x]],id[x],1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(x^y)ret+=query(id[x]+1,id[y],1,n,1);
return ret;
}
int main(){
freopen("lane.in","r",stdin);
freopen("lane.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i)f[i]=i;
for(int i=1;i<=m;++i)s[i]=read(),e[i]=read();
while(1){
int op(read());if(op==-1)break;
a[++cnt].op=op;a[cnt].x=read();a[cnt].y=read();
if(!op)ma.insert(make_pair(a[cnt].x,a[cnt].y));
else a[cnt].id=++anstop;
}
for(int i=1;i<=m;++i)if(!ma.count(make_pair(s[i],e[i]))&&!ma.count(make_pair(e[i],s[i])))tmp[++num].s=s[i],tmp[num].e=e[i];
for(int i=1;i<=num;++i){
int s(tmp[i].s),e(tmp[i].e);
int fs(find(s)),fe(find(e));
if(fs!=fe){
used[i]=1;
f[fe]=fs;
insert(s,e);insert(e,s);
}
}
dfs1(1);dfs2(1,1);build(1,n,1);
for(int i=1;i<=num;++i)if(!used[i])del(tmp[i].s,tmp[i].e);
for(int i=cnt;i>=1;--i){
if(!a[i].op)del(a[i].x,a[i].y);
else ans[a[i].id]=ask(a[i].x,a[i].y);
}
for(int i=1;i<=anstop;++i)printf("%d\n",ans[i]);
}
Hzoi_Mafia