题目描述

Description

对Samuel星球的探险已经取得了非常巨大的成就，于是科学家们将目光投向了Samuel星球所在的星系——一个巨大的由千百万星球构成的Samuel星系。 星际空间站的Samuel II巨型计算机经过长期探测，已经锁定了Samuel星系中许多星球的空间坐标，并对这些星球从1开始编号1、2、3……。 一些先遣飞船已经出发，在星球之间开辟探险航线。 探险航线是双向的，例如从1号星球到3号星球开辟探险航线，那么从3号星球到1号星球也可以使用这条航线。 例如下图所示：

在5个星球之间，有5条探险航线。 A、B两星球之间，如果某条航线不存在，就无法从A星球抵达B星球，我们则称这条航线为关键航线。 显然上图中，1号与5号星球之间的关键航线有1条：即为4-5航线。 然而，在宇宙中一些未知的磁暴和行星的冲撞，使得已有的某些航线被破坏，随着越来越多的航线被破坏，探险飞船又不能及时回复这些航线，可见两个星球之间的关键航线会越来越多。 假设在上图中，航线4-2（从4号星球到2号星球）被破坏。此时，1号与5号星球之间的关键航线就有3条：1-3，3-4，4-5。 小联的任务是，不断关注航线被破坏的情况，并随时给出两个星球之间的关键航线数目。现在请你帮助完成。

Input

第一行有两个整数N，M。表示有N个星球（1< N < 30000），初始时已经有M条航线（1 < M < 100000）。随后有M行，每行有两个不相同的整数A、B表示在星球A与B之间存在一条航线。接下来每行有三个整数C、A、B。C为1表示询问当前星球A和星球B之间有多少条关键航线；C为0表示在星球A和星球B之间的航线被破坏，当后面再遇到C为1的情况时，表示询问航线被破坏后，关键路径的情况，且航线破坏后不可恢复； C为-1表示输入文件结束，这时该行没有A,B的值。被破坏的航线数目与询问的次数总和不超过40000。

Output

对每个C为1的询问，输出一行一个整数表示关键航线数目。 注意：我们保证无论航线如何被破坏，任意时刻任意两个星球都能够相互到达。在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。

Sample Input

5 5
1 2
1 3
3 4
4 5
4 2
1 1 5
0 4 2
1 5 1
-1

Sample Output

1
3

题目分析

由于没有加边操作，且保证了最后时刻图是联通的，所以我们可以离线处理，将删边转化为加边。
删除所有边以后剩下的是一个连通图，我们求出它的任意一棵生成树，一开始的树边一定是关键路径，那么加入一条边就相当于形成了一个环，即两点之间路径上所有的边不再为关键航线，打上区间标记。
然后按照逆时间顺序，将删除的边加上，处理询问。（需要先把原来连通图中非树边也加上）
查询时，看一下路径上有多少条未标记的边就行了。
于是问题转化为：将两点间的所有边染色、询问两点间多少条边没有被染色。使用树链剖分+线段树水过

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
int n,m,cnt;
int head[30010],to[80010],net[80010];
int deep[30010],size[30010],fa[30010],son[30010],top[30010],number[30010];
struct way
{
    int x,y;
    bool use;
}edge[100100];
struct ques
{
    int tmp,x,y;
}q[100100];
struct your
{
    int x,y,sum,add;
}a[30010*5];
int tot;
void add(int x,int y) 
{ 
    net[++tot]=head[x],head[x]=tot,to[tot]=y; 
}
map<pair<int,int>,int>mp;

int f[100100];
int findx(int x) { return f[x]==x?x:f[x]=findx(f[x]); }
void kru()
{
    for(int i=1;i<=n;i++) f[i]=i;
    int num=0;
    for(int i=1;i<=m;i++)
    {
        if(num==n-1) return ;
        if(mp[make_pair(edge[i].x,edge[i].y)]) continue;
        int dx=findx(edge[i].x),dy=findx(edge[i].y);
        if(dx!=dy) f[dx]=dy,edge[i].use=1,add(edge[i].x,edge[i].y),add(edge[i].y,edge[i].x),num++;
    }
}
void dfs(int x)
{
    deep[x]=deep[fa[x]]+1;
    size[x]=1;
    for(int i=head[x];i;i=net[i])
        if(to[i]!=fa[x])
        {
            fa[to[i]]=x,dfs(to[i]);
            size[x]+=size[to[i]];
            if(size[son[x]]<size[to[i]]) son[x]=to[i];
        }
}
int num=0;
void dfs2(int x,int temp)
{
    number[x]=++num,top[x]=temp;
    if(son[x]) dfs2(son[x],temp);
    for(int i=head[x];i;i=net[i])
        if(to[i]!=fa[x]&&to[i]!=son[x]) dfs2(to[i],to[i]);
}
void build(int dx,int dy,int num)
{
    a[num].x=dx,a[num].y=dy;
    if(dx==dy)
    {
        if(dx==1) a[num].sum=0;
        else a[num].sum=1;
        return ;
    }
    int mid=(dx+dy)>>1;
    build(dx,mid,num<<1),build(mid+1,dy,num<<1|1);
    a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
    return ;
}
void pushdown(int num)
{
    a[num].add=0;
    a[num<<1].add=1,a[num<<1|1].add=1;
    a[num<<1].sum=0,a[num<<1|1].sum=0;
    return ;
}
void update(int dx,int dy,int num)
{
    if(a[num].x==dx&&a[num].y==dy)
    {
        a[num].add=1,a[num].sum=0;
        return ;
    }
    if(a[num].add) pushdown(num);
    int mid=(a[num].x+a[num].y)>>1;
    if(dx>mid) update(dx,dy,num<<1|1);
    else if(dy<=mid) update(dx,dy,num<<1);
    else update(dx,mid,num<<1),update(mid+1,dy,num<<1|1);
    a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
}
int ask(int dx,int dy,int num)
{
    if(a[num].x==dx&&a[num].y==dy) return a[num].sum;
    if(a[num].add) pushdown(num);
    int mid=(a[num].x+a[num].y)>>1;
    if(dx>mid) return ask(dx,dy,num<<1|1);
    else if(dy<=mid) return ask(dx,dy,num<<1);
    else  return ask(dx,mid,num<<1)+ask(mid+1,dy,num<<1|1);
}
void change(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        update(number[top[x]],number[x],1);
        x=fa[top[x]];
    }
    if(x==y) return ;
    if(deep[x]>deep[y]) swap(x,y);
    update(number[x]+1,number[y],1);
}
int find(int x,int y)
{
    int sum=0;
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        sum+=ask(number[top[x]],number[x],1);
        x=fa[top[x]];
    }
    if(x==y) return sum;
    if(deep[x]>deep[y]) swap(x,y);
    return sum+ask(number[x]+1,number[y],1);
}
int ans[100100];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) 
    {
        scanf("%d%d",&edge[i].x,&edge[i].y);
        if(edge[i].x>edge[i].y) swap(edge[i].x,edge[i].y);
    }
    while(1)
    {
        int tmp,x,y;
        scanf("%d",&tmp);
        if(tmp==-1) break;
        scanf("%d%d",&x,&y);
        cnt++;
        q[cnt].tmp=tmp,q[cnt].x=x,q[cnt].y=y;
        if(q[cnt].x>q[cnt].y) swap(q[cnt].x,q[cnt].y);
        if(tmp==0) mp[make_pair(q[cnt].x,q[cnt].y)]=1;
    }
    kru();
    dfs(1),dfs2(1,1),build(1,n,1);
    for(int i=1;i<=m;i++)
        if(!edge[i].use&&!mp[make_pair(edge[i].x,edge[i].y)])
            change(edge[i].x,edge[i].y);
    for(int i=cnt;i>=1;i--)
    {
        if(q[i].tmp!=1) change(q[i].x,q[i].y); 
        else ans[i]=find(q[i].x,q[i].y);
    }
    for(int i=1;i<=cnt;i++)
        if(q[i].tmp==1) printf("%d\n",ans[i]);
    return 0;
}