tarjan、并查集、树状数组、树链剖分。
时间倒流，变删边为加边。
先求一波边双联通分量，缩点。
题目保证最后还是整张图联通的。。所以就是一棵树。
现在的操作就是，将路径上的边权置0（加边时），查询两点间边权和。
可以转换成求根到点路径上边权和，置0的时候，就相当于将子树内的值都减去原边的长度，可以dfs序+树状数组。
置0那个还要写个并查集，维护当前点经过连续一段0边到达的最远的祖先。
查询的时候还得求lca。。。。就顺便写个链剖...
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ui unsigned int
using namespace std;
const int maxn=,maxm=;
struct zs{int too,pre;}e[maxm<<];int tot,last[maxn];
bool iscut[maxm<<];
struct zs1{int x,y;}a[maxm];
struct zs2{bool del;int id,x,y;}b[];
int fa[maxn],bel[maxn],dep[maxn],dfn[maxn],low[maxn],tim,L[maxn],R[maxn],TIM,sz[maxn],cha[maxn],id[maxn];
int la[maxn<<],pre[maxn<<],too[maxn<<],tt;
int An[];
int i,j,k,n,m,q,cnt;
bool gg[maxm]; int ra,fh;char rx;
inline int read(){
rx=getchar(),ra=,fh=;
while((rx<''||rx>'')&&rx!='-')rx=getchar();
if(rx=='-')fh=-,rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;
} inline int getbel(int x){return bel[x]!=x?bel[x]=getbel(bel[x]):x;} void dfs(int x,int efa){
dfn[x]=low[x]=++tim;
for(int i=last[x];i;i=e[i].pre)if(i!=efa)
if(!dfn[e[i].too])
dfs(e[i].too,i^),low[x]=min(low[x],low[e[i].too]);
else low[x]=min(low[x],dfn[e[i].too]);
if(dfn[x]==low[x]&&efa)iscut[efa]=iscut[efa^]=;
}
void dfs2(int x){
dep[x]=dep[fa[x]]+,sz[x]=;
for(int i=la[x];i;i=pre[i])
if(too[i]!=fa[x])fa[too[i]]=x,dfs2(too[i]),sz[x]+=sz[too[i]];
}
void dfs3(int x,int chain){
cha[x]=chain,L[x]=++TIM;
int i,mx=;
for(i=la[x];i;i=pre[i])if(too[i]!=fa[x]&&sz[too[i]]>sz[mx])mx=too[i];
if(!mx){R[x]=TIM;return;}
dfs3(mx,chain);
for(i=la[x];i;i=pre[i])if(too[i]!=fa[x]&&too[i]!=mx)dfs3(too[i],too[i]);
R[x]=TIM;
}
inline int getlca(int a,int b){
while(cha[a]!=cha[b]){
if(dep[cha[a]]<dep[cha[b]])swap(a,b);
a=fa[cha[a]];
}
return dep[a]<dep[b]?a:b;
}
inline void insert(int a,int b){
e[++tot].too=b,e[tot].pre=last[a],last[a]=tot,
e[++tot].too=a,e[tot].pre=last[b],last[b]=tot;
}
inline void ins(int a,int b){//printf(" %d-->%d\n",a,b);
too[++tt]=b,pre[tt]=la[a],la[a]=tt,
too[++tt]=a,pre[tt]=la[b],la[b]=tt;
}
int t[maxn];
inline void add(int l,int r,int v){//printf(" add: %d--%d v:%d\n",l,r,v);
while(l<=cnt)t[l]-=v,l+=l&-l;
r++;while(r<=cnt)t[r]+=v,r+=r&-r;
}
inline int ask(int x){/*printf("__x: %d\n",x);*/int sm=;while(x)sm+=t[x],x-=x&-x;return sm;} inline int query(int x,int y){
int lca=getlca(x,y);//printf("query: %d %d lca:%d %d %d\n",x,y,lca,getbel(x),getbel(y));
x=dep[x]+ask(L[x]),y=dep[y]+ask(L[y]),lca=dep[lca]+ask(L[lca]);//printf("dep: %d %d %d\n",x,y,lca);
return x+y-(lca<<);
}
inline void link(int x,int y){//printf("link:%d %d\n",x,y);
int i,j,tmp;
i=getbel(x),j=getbel(y);//printf(" %d %d dep:%d %d\n",i,j,dep[i],dep[j]);
while(i!=j){
if(dep[i]<dep[j])swap(i,j);
tmp=getbel(fa[i]);
add(L[i],R[i],/*dep[i]-dep[tmp]*/);//printf("i:%d tmp:%d\n",i,tmp);
bel[i]=tmp,i=bel[i];
}
} bool cmp(zs1 a,zs1 b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
inline int getpos(int x,int y){
int l=,r=m,mid;
while(l<r)
if(a[(mid=l+r>>)].x==x?(a[mid].y==y?gg[mid]:a[mid].y<y):a[mid].x<x)l=mid+;else r=mid;
return l;
}
int main(){
n=read(),m=read();register int i;
for(i=;i<=m;i++){
j=read(),k=read();
if(j>k)swap(j,k);
a[i].x=j,a[i].y=k;
}
sort(a+,a++m,cmp);
int id1;i=;
for(id1=read();id1!=-;id1=read()){
i++,j=b[i].x=read(),k=b[i].y=read();
if(j>k)swap(j,k);
if(!id1)b[i].del=,gg[b[i].id=getpos(j,k)]=;
}q=i; tot=;
for(i=;i<=m;i++)if(!gg[i])insert(a[i].x,a[i].y);
dfs(,);
for(i=;i<=n;i++)bel[i]=i;
for(i=;i<=tot;i+=)if(!iscut[i])
bel[getbel(e[i].too)]=getbel(e[i^].too);
for(i=;i<=n;i++)if(getbel(i)==i)id[i]=++cnt;
for(i=;i<=q;i++){
if(b[i].del)a[b[i].id].x=id[bel[a[b[i].id].x]],a[b[i].id].y=id[bel[a[b[i].id].y]];
b[i].x=id[getbel(b[i].x)],b[i].y=id[getbel(b[i].y)];
}
for(i=;i<=tot;i+=)if(iscut[i])ins(id[bel[e[i].too]],id[bel[e[i^].too]]);
for(i=;i<=cnt;i++)bel[i]=i;
fa[]=,dfs2(),dfs3(,);
// for(i=1;i<=cnt;i++)printf(" i:%d dfn:%d bel:%d L:%d R:%d dep:%d\n",i,L[i],cha[i],L[i],R[i],dep[i]); for(i=q;i;i--)//{
if(!b[i].del)An[i]=query(b[i].x,b[i].y);
else link(a[b[i].id].x,a[b[i].id].y);
// for(j=1;j<=n;j++)printf(" %d",ask(j));puts("");
// }
for(i=;i<=q;i++)if(!b[i].del)printf("%d\n",An[i]);
}