## Bridges

### 题目描述

An edge in an undirected graph is a bridgeif after removing it the graph will be disconnected.
Given an undirected connected graph, you are allowed to add one edge between any pair of nodes so that the total number of bridges in the graph is minimized.

### 输入格式

The first line of input contains $T$ ($1 \le T \le 64$)that represents the number of test cases.
The first line of each test case contains two integers: $N$ ($3 \le N \le 100,000$) and $M$ ($N-1 \le M \le 100,000$),where $N$ is the number of nodes, and $M$ is the number of edges.
Each of the following $M$ lines contains two space-separated integers: $X\ Y$ ($1 \le X,Y \le N$)($X \neq Y$), which means that there is an edge between node $X$ and node $Y$.
It is guaranteed that each pair of nodes is connected by at most one edge.
Test cases are separated by a blank line.

### 输出格式

For each test case, print a single line with the minimum possible number of bridges after adding one edge.

### 样例输入

2
7 7
1 2
2 3
3 1
3 4
4 5
4 6
6 7

3 3
1 2
2 3
3 1


### 样例输出

1
0


## 题解

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int x,y;
struct aa{
int to,nxt;
}p[200009];
int h[100009],len;
aa p2[200009];
int h2[200009],len2;
p[++len].to=y;
p[len].nxt=h[x];
h[x]=len;
}
int to[200009];
int dfn[100009],low[100009];
int uu[100009],lu;
int ut;
int ans,as,ss;
void tarjan(int u,int fa){
uu[++lu]=u;
dfn[u]=low[u]=++ut;
for(int j=h[u];j;j=p[j].nxt){
if(p[j].to==fa) continue;
if(dfn[p[j].to]==0){
tarjan(p[j].to,u);
low[u]=min(low[u],low[p[j].to]);
}else low[u]=min(low[u],dfn[p[j].to]);
}
if(dfn[u]==low[u]){
while(uu[lu]!=u) to[uu[lu--]]=u;
to[uu[lu--]]=u;
}
}
void dfs(int u,int s,int fa){
if(s>ans){ans=s;as=u;}
for(int j=h2[u];j;j=p2[j].nxt){
if(p2[j].to==fa) continue;
dfs(p2[j].to,s+1,u);
}
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
len=len2=0;
memset(h,0,sizeof(h));
memset(h2,0,sizeof(h2));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
for(int j=1;j<=m;j++){
scanf("%d%d",&x,&y);
}
tarjan(1,0);
ss=0;
for(int u=1;u<=n;u++){
for(int j=h[u];j;j=p[j].nxt){
x=to[u];y=to[p[j].to];
if(x!=y){
p2[++len2].to=y;
p2[len2].nxt=h2[x];
h2[x]=len2;
ss++;
}
}
}
ss/=2;
ans=0;
dfs(to[1],0,0);
dfs(as,0,0);
printf("%d\n",ss-ans);
}
return 0;
}