思路

简化题意：动态删边，询问两点间的割边数量。

如果真按照题目所说，动态删边，然后求两点间的割边数量是比较困难的，那么我们考虑反向来看，对最终图，动态加边，求两点间的割边数量。

这个转化就让问题变得简单许多。

我们考虑加入边的两种情况

  1. 与 在同一个强联通分量里，不影响割边数量

  2. 与 在不同强联通分量里， 那么 到 路径上的割边就都不是了。

对最终图缩点，不同强联通分量之间的边就是最终的割边，初始边权均为 1，图变为一棵树。对这棵树树剖，建线段树维护边权，对于加边操作，我们可以将 所在联通分量到 所在联通分量路径上的边权置为 0。询问时直接询问 到 路径上的权值和。

时间复杂度 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 Int;
namespace FastIO{
    class In{
        public:
            template<typename T>
            inline In &operator>>(T &x)
            {
                x=0;bool f=0;
                char c=getchar();
                while(c<'0'||c>'9')
                    f|=(c=='-'),c=getchar();
                while(c>='0'&&c<='9')
                    x=x*10+c-'0',c=getchar();
                if(c=='.')
                {
                    c=getchar();double dot=0.1;
                    while(c>='0'&&c<='9')
                        x+=(c-'0')*dot,dot*=0.1,c=getchar();
                }
                return (f?x=-x:x),*this;
            }
            inline In &operator>>(char &x)
            {
                while(isspace(x=getchar()));
                return *this;
            }
            inline In &operator>>(char *x)
            {
                char c=getchar();
                while(isspace(c)) c=getchar();
                while(!isspace(c)&&~c) *(x++)=c,c=getchar();
                return *x=0,*this;
            }
            inline In &operator>>(string &x)
            {
                char c=getchar();x.clear();
                while(isspace(c)) c=getchar();
                while(!isspace(c)&&~c) x.push_back(c),c=getchar();
                return *this;
            }
    };
    class Out{
        private:
            char buf[35];
            short dot=6,top=0;
        public:
            template<typename T>
            inline Out &operator<<(T x)
            {
                if(x<0) putchar('-'),x=-x;
                do buf[++top]=x%10,x/=10;while(x);
                while(top) putchar(buf[top--]^'0');
                return *this;
            }
            inline Out &operator<<(char c){return putchar(c),*this;}
            inline Out &operator<<(string x)
            {
                for(auto c:x) putchar(c);
                return *this;
            }
            inline Out &operator<<(char *x)
            {
                while(*x) putchar(*(x++));
                return *this;
            }
            inline Out &operator<<(const char *x)
            {
                while(*x) putchar(*(x++));
                return *this;
            }
            inline Out &operator<<(double x)
            {
                snprintf(buf,sizeof(buf),"%.*lf",dot,x);
                return (*this)<<buf;
            }
            inline Out setdot(const int n){return dot=n,*this;}
    };
    In fin;Out fout;
    inline Out &setdot(const int n,Out& out=fout){return fout.setdot(n),out;}
    inline In &getline(char *x,In& in=fin)
    {
        char c=getchar();
        while(!(c==' '||!isspace(c))) c=getchar();
        while(c==' '||!isspace(c)) (*x++)=c,c=getchar();
        return *x=0,in;
    }
    inline In &getline(string &x,In& in=fin)
    {
        char c=getchar();x.clear();
        while(!(c==' '||!isspace(c))) c=getchar();
        while(c==' '||!isspace(c)) x.push_back(c),c=getchar();
        return in;
    }
}
using namespace FastIO;
const int N=3e5+10,M=4e5+10;
vector<int>G[N],E[N];
struct Query{
    int op,x,y;
}q[M];
int n,m,k;
int x[N],y[N];
map<pair<int,int>,bool>vis;
int dfn[N],low[N],t=0;
int St[N],top=0;
int Be[N],o=0,rt=1;
bool in[N];
int Siz[N],Dep[N],Fa[N];
int Top[N],Son[N];
int Ans[M];
void Tarjan(int now,int from)
{
    in[St[++top]=now]=1;
    dfn[now]=low[now]=++t;
    for(int to:G[now])
    {
        if(to==from) continue;
        if(!dfn[to]){
            Tarjan(to,now);
            low[now]=min(low[now],low[to]);
        }
        else if(in[now])
            low[now]=min(low[now],dfn[to]);
    }
    if(low[now]==dfn[now])
    {
        ++o;int x;
        do{
            in[x=St[top--]]=0;
            Be[x]=o;
        }while(x^now);
    }
}
void dfs(int now,int from)
{
    Fa[now]=from;Siz[now]=1;
    for(int to:E[now])
    {
        if(to==from) continue;
        Dep[to]=Dep[now]+1;
        dfs(to,now);
        Siz[now]+=Siz[to];
        if(Siz[to]>Siz[Son[now]]) Son[now]=to;
    }
    return;
}
void redfs(int now,int top)
{
    dfn[now]=++t;Top[now]=top;
    if(Son[now]) redfs(Son[now],top);
    for(int to:E[now])
        if(to==Son[now]||to==Fa[now]) continue;
        else redfs(to,to);
    return;
}
int sum[N<<2],tag[N<<2];
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
void push_up(int x){sum[x]=sum[lc(x)]+sum[rc(x)];}
void addtag(int x){sum[x]=0,tag[x]=1;}
void push_down(int x)
{
    if(!tag[x]) return;
    addtag(lc(x)),addtag(rc(x)),tag[x]=0;
}
void build(int l,int r,int x)
{
    if(l==r)
        return void(sum[x]=1);
    int mid=(l+r)>>1;
    build(l,mid,lc(x)),build(mid+1,r,rc(x));
    return push_up(x);
}
void modify(int p,int q,int l=1,int r=o,int x=1)
{
    if(p<=l&&q>=r) return addtag(x);
    push_down(x);
    int mid=(l+r)>>1;
    if(p<=mid) modify(p,q,l,mid,lc(x));
    if(q>mid) modify(p,q,mid+1,r,rc(x));
    return push_up(x);
}
int query(int p,int q,int l=1,int r=o,int x=1)
{
    if(p<=l&&q>=r) return sum[x];
    push_down(x);
    int mid=(l+r)>>1;
    if(q<=mid) return query(p,q,l,mid,lc(x));
    if(p>mid) return query(p,q,mid+1,r,rc(x));
    return query(p,q,l,mid,lc(x))+query(p,q,mid+1,r,rc(x));
}
void Modify(int x,int y)
{
    while(Top[x]^Top[y]){
        if(Dep[Top[x]]<Dep[Top[y]]) swap(x,y);
        modify(dfn[Top[x]],dfn[x]);x=Fa[Top[x]];
    }
    if(Dep[x]>Dep[y]) swap(x,y);
    if(x^y) modify(dfn[x]+1,dfn[y]);
    return;
}
int Query(int x,int y)
{
    int res=0;
    while(Top[x]^Top[y]){
        if(Dep[Top[x]]<Dep[Top[y]]) swap(x,y);
        res+=query(dfn[Top[x]],dfn[x]);x=Fa[Top[x]];
    }
    if(Dep[x]>Dep[y]) swap(x,y);
    if(x^y) res+=query(dfn[x]+1,dfn[y]);
    return res;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>x[i]>>y[i];
    while(true){
        int op,x,y;
        fin>>op;
        if((!~op)) break;
        else{
            fin>>x>>y;
            q[++k]={op,x,y};
            if(!q[k].op)vis[{x,y}]=vis[{y,x}]=1;
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(vis[{x[i],y[i]}]) continue;
        G[x[i]].push_back(y[i]);
        G[y[i]].push_back(x[i]);
    }
    Tarjan(rt,0);
    for(int now=1;now<=n;now++)
    {
        for(int to:G[now])
        {
            if(Be[now]^Be[to])
                E[Be[now]].push_back(Be[to]);
        }
    }
    dfs(Be[rt],0),t=0,redfs(Be[rt],Be[rt]);
    build(1,o,1);
    for(int i=1;i<=k;i++)
        q[i].x=Be[q[i].x],q[i].y=Be[q[i].y];
    for(int i=k;i;i--)
        if(q[i].op) Ans[i]=Query(q[i].x,q[i].y);
        else Modify(q[i].x,q[i].y);
    for(int i=1;i<=k;i++)
        if(q[i].op) fout<<Ans[i]<<'\n';
    return 0;
}