洛谷上是可以过掉的。NFLSOJ上加强数据，还卡常，所以 90pts。
首先倒着做很好想。对于最终的图，我们可以 tarjan 缩点然后建树，边权为 \(1\)，表示一条割边。然后每次连两个点的时候就把树上这一段路径赋值为 \(0\)。查询就是树上路径和。这些操作都可以点赋边权然后树剖来做。所以你就得到了 \(200+\) 行的 \(log^2\) 答辩做法。
我才不会告诉你区间赋 0 pushdown 的时候由于 tag 初始为 0 调了将近 1h
//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
using namespace std;
int n,m,q;
struct edge{
int u,v;
}e1[500005];
struct node{
int c,u,v,ans;
}b[500005];
map<pii,bool> mp;
int head[200005],tot=1,timer,cnt;
int dfn[200005],low[200005],stk[200005],top;
int col[200005];
struct Node{
int to,nxt;
}e[500005];
void add(int u,int v){
e[++tot]={v,head[u]};
head[u]=tot;
}
void tarjan(int x,int fe){
dfn[x]=low[x]=++timer;
stk[++top]=x;
for(int i=head[x];i;i=e[i].nxt){
int tmp=e[i].to;
if(!dfn[tmp]){
tarjan(tmp,i);
low[x]=min(low[x],low[tmp]);
}
else if(i^1^fe){
low[x]=min(low[x],dfn[tmp]);
}
}
if(dfn[x]==low[x]){
cnt++;
do{
col[stk[top--]]=cnt;
}while(stk[top+1]!=x);
}
}
int fa[200005],dep[200005],siz[200005],DFN[200005];
int Timer,Top[200005],son[200005],u,v;
vector<int> a[200005];
struct SGT{
struct node{
int l,r,sum,tag;
}tr[800005];
void build(int i,int l,int r){
tr[i].l=l,tr[i].r=r,tr[i].tag=-1;
if(l==r){
tr[i].sum=1;
return ;
}
int mid=(l+r)>>1;
build(ls(i),l,mid),build(rs(i),mid+1,r);
tr[i].sum=tr[ls(i)].sum+tr[rs(i)].sum;
}
void pushdown(int i){
if(tr[i].tag!=-1){
tr[ls(i)].tag=tr[i].tag;
tr[rs(i)].tag=tr[i].tag;
tr[ls(i)].sum=(tr[ls(i)].r-tr[ls(i)].l+1)*tr[i].tag;
tr[rs(i)].sum=(tr[rs(i)].r-tr[rs(i)].l+1)*tr[i].tag;
tr[i].tag=-1;
}
}
void upd(int i,int l,int r,int k){
if(tr[i].l>=l&&tr[i].r<=r){
tr[i].sum=(tr[i].r-tr[i].l+1)*k;
tr[i].tag=k;
return ;
}
pushdown(i);
int mid=(tr[i].l+tr[i].r)>>1;
if(l<=mid) upd(ls(i),l,r,k);
if(mid<r) upd(rs(i),l,r,k);
tr[i].sum=tr[ls(i)].sum+tr[rs(i)].sum;
}
int query(int i,int l,int r){
if(tr[i].l>=l&&tr[i].r<=r) return tr[i].sum;
pushdown(i);
int mid=(tr[i].l+tr[i].r)>>1,ans=0;
if(l<=mid) ans+=query(ls(i),l,r);
if(mid<r) ans+=query(rs(i),l,r);
return ans;
}
}sgt;
void dfs1(int x,int Fa){ //fa,siz,dep,mxson
fa[x]=Fa,siz[x]=1,dep[x]=dep[Fa]+1;
int mx=-1;
for(int i=0;i<a[x].size();i++){
int tmp=a[x][i];
if(tmp==Fa) continue;
dfs1(tmp,x),siz[x]+=siz[tmp];
if(siz[tmp]>mx) mx=siz[tmp],son[x]=tmp;
}
}
void dfs2(int x,int Fa,int t){ //dfn,top
DFN[x]=++Timer;
Top[x]=t;
if(!son[x]) return ;
dfs2(son[x],x,t);
for(int i=0;i<a[x].size();i++){
int tmp=a[x][i];
if(tmp==Fa||tmp==son[x]) continue;
dfs2(tmp,x,tmp);
}
}
int Query(int x,int y){
int ans=0;
while(Top[x]!=Top[y]){
if(dep[Top[x]]<dep[Top[y]]) swap(x,y);
ans+=sgt.query(1,DFN[Top[x]],DFN[x]);
x=fa[Top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=sgt.query(1,DFN[x]+1,DFN[y]);
return ans;
}
void Upd(int x,int y,int k){
while(Top[x]!=Top[y]){
if(dep[Top[x]]<dep[Top[y]]) swap(x,y);
sgt.upd(1,DFN[Top[x]],DFN[x],k);
x=fa[Top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
// cout<<"***"<<DFN[x]+1<<' '<<DFN[y]<<endl;
sgt.upd(1,DFN[x]+1,DFN[y],k);
}
signed main(){
// freopen("lane.in","r",stdin);
// freopen("lane.out","w",stdout);
IOS;TIE;
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>e1[i].u>>e1[i].v;
while(1){
q++;
cin>>b[q].c;
if(b[q].c==-1){
q--;
break;
}
cin>>b[q].u>>b[q].v;
if(b[q].c==0){
mp[mk(b[q].u,b[q].v)]=1;
mp[mk(b[q].v,b[q].u)]=1;
}
}
for(int i=1;i<=m;i++){
if(!mp[mk(e1[i].u,e1[i].v)]){
add(e1[i].u,e1[i].v);
add(e1[i].v,e1[i].u);
}
}
tarjan(1,0);
for(int i=1;i<=m;i++){
if(!mp[mk(e1[i].u,e1[i].v)]){
int x=col[e1[i].u],y=col[e1[i].v];
if(x^y) a[x].pb(y),a[y].pb(x);
}
}
dfs1(1,0);
dfs2(1,0,1);
sgt.build(1,1,n);
// for(int i=1;i<=n;i++) cout<<col[i]<<' ';
// cout<<endl;
// for(int i=1;i<=n;i++) cout<<DFN[col[i]]<<' ';
// cout<<endl;
for(int i=q;i>=1;i--){
int x=col[b[i].u],y=col[b[i].v];
if(b[i].c==1) b[i].ans=Query(x,y);
else Upd(x,y,0);
// for(int j=1;j<=n;j++){
// cout<<sgt.query(1,DFN[col[j]],DFN[col[j]])<<endl;
// }
}
for(int i=1;i<=q;i++){
if(b[i].c==1) cout<<b[i].ans<<'\n';
}
return 0;
}
/*
6 6 3
1 2
1 3
3 4
2 4
5 4
3 6
1 5 6
1 1 5
1 5 6
*/