( ext{Solution:})
观察题目，说要有两条互相分离的路径。
那么，这意味着什么？
注意到 这里叫做，互相分离。
那也就是说，如果我把一条路割断，它可以通过另外一条路到达这个点。
也就是说，这张图没有割边，是边双。
那么，思路就很自然了，先写一个求边双，然后把边双缩起来，容易知道剩下的图组成一棵树。
那么，如何用最少的边把树变成边双？
有一个自然的结论：边数最少的边双是环。
那么，考虑如何在树上构造环使得其成为边双：自然想到连接两个叶子就是最优的。
所以，我们每次连一条边就可以解决两个叶子。
那么，我们只需要把缩点后的图的树的叶子个数求出来，除以 (2) 上取整即可。
因为奇数剩下的点需要单独做一遍。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int head[N],Head[N],tto,tot=1;
struct E{int nxt,to;}e[N<<1],edge[N<<1];
map<int,map<int,int> >mp;
inline void link(int u,int v,int w=0){
if(w){
edge[++tto]=(E){Head[u],v};
Head[u]=tto;
return;
}
e[++tot]=(E){head[u],v};
head[u]=tot;
}
int dfstime,dfn[N],low[N],vis[N],c[N],n,m;
inline int Min(int x,int y){return x<y?x:y;}
int node=0,col[N],deg[N];
void tarjan(int x,int pos){
dfn[x]=low[x]=++dfstime;
for(int i=head[x];i;i=e[i].nxt){
if(i==(pos^1))continue;
int j=e[i].to;
if(!dfn[j]){
tarjan(j,i);
low[x]=Min(low[x],low[j]);
if(low[j]>dfn[x])vis[i]=vis[i^1]=1;
}
else low[x]=Min(low[x],dfn[j]);
}
}
struct Rem{int u,v;}rem[N];
void dfs(int x){
c[x]=node;
for(int i=head[x];i;i=e[i].nxt){
if(vis[i])continue;
int j=e[i].to;
if(c[j])continue;
dfs(j);
}
}
int main(){
freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int x,y;
scanf("%d%d",&x,&y);
link(x,y);
link(y,x);
rem[i]=(Rem){x,y};
}
for(int i=1;i<=n;++i)if(!dfn[i])++node,tarjan(i,0);
for(int i=1;i<=n;++i){
if(!c[i]){
++node;
dfs(i);
}
}
for(int i=1;i<=m;++i){
int u=c[rem[i].u];
int v=c[rem[i].v];
if(u==v)continue;
if(mp[u][v])continue;
mp[u][v]=1;
mp[v][u]=1;
link(u,v,1);
link(v,u,1);
deg[u]++;
deg[v]++;
}
// for(int i=1;i<=n;++i)printf("%d %d:
",i,c[i]);
// for(int i=1;i<=node;++i)printf("%d %d
",i,deg[i]);
int cnt=0;
for(int i=1;i<=node;++i)if(deg[i]==1)cnt++;
if(cnt&1)cnt++;
cnt>>=1;
printf("%d
",cnt);
return 0;
}