题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4612
所有图论题都要往树上考虑
题意：给一张图，仅允许添加一条边，问能干掉的最多条桥有多少。
必须解决重边的问题，最后会说。
首先tarjan跑出所有的双连通分量和是桥的边还有桥的数量，这非常重要。接着缩点重新建图，然后两遍dfs找出两个在树上距离最远的点。我的想法就是把这条最长的链连成一个环，让它成为一个双连通分量，这样的效果是最好的。最后就是用桥的数量减去树直径再减一就得到了剩下的桥的数量了。求树直径的时候重用了dfn数组，不要以为是错的就好。
重边真的好烦人啊，我像处理离散化那样unique了一下，发现是不可行的。最终还是参考了bin神的方法，在边的结构体里加一个记号来标记这个边是不是重边，也就是出现重边的话，那这几条重边就不是桥啦。如果按照我之前的做法，重边会被删掉，所以桥的数量会增多，显然是不对的。
/*
━━━━━┒ギリギリ♂ eye！
┓┏┓┏┓┃キリキリ♂ mind！
┛┗┛┗┛┃＼○／
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define fr first
#define sc second
#define cl clear
#define BUG puts("here!!!")
#define W(a) while(a--)
#define pb(a) push_back(a)
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%lld", &a)
#define Rs(a) scanf("%s", a)
#define Cin(a) cin >> a
#define FRead() freopen("in", "r", stdin)
#define FWrite() freopen("out", "w", stdout)
#define Rep(i, len) for(int i = 0; i < (len); i++)
#define For(i, a, len) for(int i = (a); i < (len); i++)
#define Cls(a) memset((a), 0, sizeof(a))
#define Clr(a, x) memset((a), (x), sizeof(a))
#define Full(a) memset((a), 0x7f7f, sizeof(a))
#define lp p << 1
#define rp p << 1 | 1
#define pi 3.14159265359
#define RT return
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef map<string, int> msi;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb; const int maxn = ;
const int maxm = ; typedef struct Edge {
int u, v;
int next;
bool cut, r;
Edge() { next = -; cut = ; }
}Edge; typedef struct Tmp {
int u, v;
Tmp() {}
Tmp(int uu, int vv) : u(uu), v(vv) {}
bool operator==(Tmp p) { RT u == p.u && v == p.v; }
}Tmp; int head[maxn], ecnt;
int n, m;
int bcnt, idx;
int dfn[maxn], low[maxn];
int stk[maxn], top;
int belong[maxn];
bool instk[maxn];
Edge edge[maxm];
Tmp tmp[maxm];
vector<int> G[maxn]; bool cmp(Tmp x, Tmp y) {
if(x.u == y.u) RT x.v < y.v;
RT x.u < y.u;
} void init() {
memset(edge, , sizeof(edge));
memset(head, -, sizeof(head));
memset(instk, , sizeof(instk));
memset(dfn, , sizeof(dfn));
memset(low, , sizeof(low));
memset(belong, , sizeof(belong));
ecnt = top = bcnt = idx = ;
} void adde(int uu, int vv, bool p) {
edge[ecnt].u = uu;
edge[ecnt].v = vv;
edge[ecnt].cut = ;
edge[ecnt].r = p;
edge[ecnt].next = head[uu];
head[uu] = ecnt++;
} void tarjan(int u, int p, int r) {
int v = u;
dfn[u] = low[u] = ++idx;
stk[++top] = u;
instk[u] = ;
for(int i = head[u]; ~i; i=edge[i].next) {
v = edge[i].v;
if(v == p && (!r)) continue;
// if(v == p) continue;
if(!dfn[v]) {
tarjan(v, u, edge[i].r);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]) edge[i].cut = edge[i^].cut = ;
}
else if(instk[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]) {
bcnt++;
do {
v = stk[top--];
instk[v] = ;
belong[v] = bcnt;
} while(v != u);
}
} void dfs(int u) {
Rep(i, G[u].size()) {
int v = G[u][i];
if(dfn[v] != -) continue;
dfn[v] = max(dfn[v], dfn[u] + );
dfs(v);
}
} inline bool scan_d(int &num) {
char in;bool IsN=false;
in=getchar();
if(in==EOF) return false;
while(in!='-'&&(in<''||in>'')) in=getchar();
if(in=='-'){ IsN=true;num=;}
else num=in-'';
while(in=getchar(),in>=''&&in<=''){
num*=,num+=in-'';
}
if(IsN) num=-num;
return true;
} int main() {
// FRead();
int u, v;
while(~scan_d(n) && ~scan_d(m) && n + m) {
init();
Rep(i, n+) G[i].cl();
Rep(i, m) {
scan_d(u); scan_d(v);
if(u == v) continue;
if(u > v) swap(u, v);
tmp[i] = Tmp(u, v);
}
sort(tmp, tmp+m, cmp);
// m = unique(tmp, tmp+m) - tmp;
Rep(i, m) {
u = tmp[i].u; v = tmp[i].v;
if(i == || (tmp[i].u != tmp[i-].u || tmp[i].v != tmp[i-].v)) {
if(i < m - && (tmp[i].u == tmp[i+].u && tmp[i].v == tmp[i+].v)) {
adde(u, v, ); adde(v, u, );
}
else {
adde(u, v, ); adde(v, u, );
}
}
}
tarjan(, , );
For(u, , n+) {
for(int i = head[u]; ~i; i=edge[i].next) {
if(edge[i].cut) {
v = edge[i].v;
G[belong[u]].pb(belong[v]);
}
}
}
Clr(dfn, -); dfn[] = ;
dfs();
int pos = ;
For(i, , bcnt+) if(dfn[i] > dfn[pos]) pos = i;
Clr(dfn, -); dfn[pos] = ;
dfs(pos);
int ret = ;
Rep(i, bcnt+) {
ret = max(ret, dfn[i]);
}
printf("%d\n", bcnt - ret - );
}
RT ;
}