1 #pragma comment(linker,"/STACK:100000000,100000000")//阔栈的语句 2 #include <stdio.h> 3 #include <string.h> 4 #include <vector> 5 #define pb push_back 6 using namespace std; 7 const int maxn = 200002; 8 const int maxm = 1000002; 9 struct EDGE{10     int next, to, vis;11 }edge[maxm*2];//记录边，vis表示这一条边是否被访问12 struct GEEDGE {13     int u, to;14 }geedge[maxm];//记录割边15 int n,m,time,top,type,getot,cnt;//time是时间戳,type标记连通块,getot割边的数量，cnt边数16 int head[maxn],st[maxn],dfn[maxn],low[maxn],belo[maxn];//belo[i],表示i属于哪个连通块17 int start,ans1,ans,u,v;18 void init(){19     time=top=type=getot=cnt=0;20     memset(head,-1,sizeof(head));21     memset(dfn,0,sizeof(dfn));22     memset(low,0,sizeof(low));23     memset(belo,0,sizeof(belo));24 }25 void add(int u,int v){26    edge[cnt].to=v;27    edge[cnt].next=head[u];28    edge[cnt].vis=0;29    head[u]=cnt++;30 }31 void dfs(int u) {32     low[u] = dfn[u] = ++time;33     st[++top] = u;34     for(int i = head[u];i != -1;i = edge[i].next) {35         if(edge[i].vis)    continue;36         edge[i].vis = edge[i^1].vis = 1;37         int to = edge[i].to;38         if(!dfn[to]) {39             dfs(to);40             low[u] = min(low[u], low[to]);41             if(low[to] > dfn[u]) {//表示找到一个连通块42                 type++;43                 int v;44                 do {45                     v = st[top--];46                     belo[v] = type;//表示v属于第type个连通块47                 } while(v != to);48                 geedge[++getot].u = u;//记录割边的起点49                 geedge[getot].to = to;//记录割边的另一个点50             }51         }52         else53             low[u] = min(low[u], low[to]);54     }55 }56 void DFS(int len,int fa,int now){//求树的直径57     if(len>ans){58         ans=len;59         start=now;60     }61     for(int i=head[now];i!=-1;i=edge[i].next){62         int v=edge[i].to;63         if(v!=fa) DFS(len+1,now,v);64     }65 }66 int main(){67      while(~scanf("%d%d",&n,&m)&&n){68          init();69          for(int i=1;i<=m;i++){70             scanf("%d%d",&u,&v);71             add(u,v);72             add(v,u);73          }74          for(int i=1;i<=n;i++)75             if(!dfn[i])76               dfs(i);77          ans1=getot;78          memset(head,-1,sizeof(head));cnt=0;//刷新边，接下来从新加边79          for(int i=1;i<=ans1;i++){80             add(belo[geedge[i].to],belo[geedge[i].u]);81             add(belo[geedge[i].u],belo[geedge[i].to]);82          }83          ans = 0;84          DFS(0,-1,1);//85          ans=0;86          DFS(0,-1,start);//两遍DFS求树的直径87         printf("%d\n", getot-ans);88      }89 }