试题描述

SGOI 旅游局在 SG-III 星团开设了旅游业务，每天有数以万计的地球人来这里观光，包括联合国秘书长，各国总统和 SGOI 总局局长等。旅游线路四通八达，每天都有众多的载客太空飞船在星团的星球之间来往穿梭，他们保证了任意两个星球之间总是可以通过航道到达。

但是，最近由于财政出现了困难，一些一些太空飞船也过于古老，又没有足够的资金购买新产品，所有只好取消一些航道。如果某一条航道的删除使得一些星球不能到达，那么这条航道是不能删除的，称之为“主要行道”。

SGOI 旅游局局长希望知道主要行道的数目，但是航道较多，他不能手工计算，于是，他委托你写一个程序，计算主要航道数目。

输入

输入文件包含若干组数据。

每组数据的首行有两个数 m,n。星球的编号从 1 到 m。

以下 n 行每行用两个整数 a,b 描述一条航道的信息，表示从星球 a 到星球 b 是有航道的。数据由 SGOI 旅游局提供，你无需担心数据有错。

输入文件以一行0 0为结束。

输出

输出文件共有 C 行，第 i 行仅有一个数，表示第 i 组输入数据的主要行道数目。

输入示例

2 1

1 2

0 0

输出示例

1

其他说明

数据范围与提示

1≤n,m≤15000,,1≤a,b≤m

---

一个割边的弱智板子，就很舒服

还不会割边的点这里（超详细）：

下面给出代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f;}inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ;}int n,m;int head[100006],nxt[200006],to[200006];int total=0;void add(int x,int y){ total++; to[total]=y; nxt[total]=head[x]; head[x]=total; return ;}int dfn[100006],low[100006];int tot=0,ans=0;void Tarjan(int x,int fa){ dfn[x]=low[x]=++tot; for(int e=head[x];e;e=nxt[e]){ if(!dfn[to[e]]){ Tarjan(to[e],x); low[x]=min(low[x],low[to[e]]); if(low[to[e]]>dfn[x]) ans++; } else if(to[e]!=fa) low[x]=min(low[x],dfn[to[e]]); } return ;}int main(){ while(cin>>n>>m){ if(!n&&!m) return 0; total=tot=0,ans=0;; memset(head,0,sizeof(head)); memset(dfn,0,sizeof(dfn)); for(int i=1;i<=m;i++){ int x=rd(),y=rd(); add(x,y),add(y,x); } Tarjan(1,1); write(ans); puts(""); } return 0;}