一条边 $(u,v)$ 能被选当且仅当它属于所有奇环，且不属于所有偶环。先求出 dfs 生成树，我们知道若有一条返祖边，则对应着一个环，根据深度判断其奇偶性即可。用树上差分维护一条边被奇环/偶环经过了多少次，最后统计答案。

$O(n+m)$。

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define pii pair<int,int>
#define fir first
#define sec second
const int N=1e5+7,M=2e5+7;
int vis[N],dep[N],n,m,od[N],ed[N],oc[M],ec[M],cnt;
vector<pii> g[N];
void dfs(int u,int f,int pe){
	vis[u]=1;
	for(auto tmp:g[u]){
		int v=tmp.fir,id=tmp.sec;
		if(id==pe) continue;
		if(!vis[v]){
			dep[v]=dep[u]+1;
			dfs(v,u,id);
			oc[id]=od[v];
			ec[id]=ed[v];
			od[u]+=od[v];
			ed[u]+=ed[v];
		}
		else if(dep[v]<dep[u]){
			if((dep[u]^dep[v])&1){
				ed[u]++,ed[v]--;ec[id]=1;
			}
			else{
				cnt++,od[u]++,od[v]--,oc[id]=1;
			}
		}
	}
}
signed main()
{
	cin>>n>>m;
	rep(i,1,m){
		int u,v;
		cin>>u>>v;
		g[u].push_back({v,i});
		g[v].push_back({u,i});
	}
	rep(i,1,n) if(!vis[i]) dfs(i,0,0);
	int ans=0;
	rep(i,1,m){
		if(oc[i]==cnt&&!ec[i]) ans++;
	}
	cout<<ans<<"\n";
	return 0;
}