#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()
struct SegmentTree{
private:
int n;
vector<long long> nodes;
public:
void init(int N){ //初期化する O(N)
nodes.clear();
n = 1;
while(n < N) n *= 2;
n = 2 * n -1;
for(int i=0; i<n; i++) nodes.push_back(LLONG_MAX);
}
void update(int i, long long x){ //値を変更する O(log N)
i += n / 2;
nodes[i] = x;
while(i > 0){
i = (i-1)/2; //親の取得は(i-1)/2
nodes[i] = min(nodes[i*2+1], nodes[i*2+2]); //子の取得はi*2+1,i*2+2
}
}
long long minimum(int a, int b, int k=0, int l=0, int r=-1){ //[a,b)の最小値を求める O(log N)
if(r == -1) r = n/2+1;
if(r <= a || b <= l) return LLONG_MAX; //交差する場合
if(a <= l && r <= b) return nodes[k]; //完全に含む場合
long long valueL = minimum(a, b, k*2+1, l, (l+r)/2);
long long valueR = minimum(a, b, k*2+2, (l+r)/2, r);
return min(valueL, valueR);
}
long long m;
long long find(int a, int b, int k=0, int l=0, int r=-1){
if(r == -1){
m = minimum(a, b);
r = (n+1)/2;
}
if(r <= a || b <= l) return LLONG_MAX; //交差する場合
if(r-l == 1){
if(nodes[k] == m) return l;
else return LLONG_MAX;
}
if(a <= l && r <= b){ //完全に含む場合
long long valueL = minimum(a, b, k*2+1, l, (l+r)/2);
long long valueR = minimum(a, b, k*2+2, (l+r)/2, r);
if(valueL <= valueR) return find(a, b, k*2+1, l, (l+r)/2);
else return find(a, b, k*2+2, (l+r)/2, r);
}
long long valueL = find(a, b, k*2+1, l, (l+r)/2);
long long valueR = find(a, b, k*2+2, (l+r)/2, r);
return min(valueL, valueR);
}
};
int N,M;
vector<pair<int,int> > edge;
bool ki[200000] = {};
vector<pair<int,int> > tonari[100000];
bool already[100000] = {};
int dfs_order[100000];
int par[100000];
vector<int> child[100000];
int c = 0;
vector<pair<int,int> > other;
void dfs(int now){
int next = c-1;
for(int i=0; i<tonari[now].size(); i++){
if(already[tonari[now][i].first]) continue;
already[tonari[now][i].first] = true;
ki[tonari[now][i].second] = true;
par[c] = next;
dfs_order[tonari[now][i].first] = c;
child[next].push_back(c);
c++;
dfs(tonari[now][i].first);
}
}
int d[100000] = {};
int depth(int i){
if(par[i] == i) return 0;
if(d[i] != 0) return d[i];
return d[i] = 1 + depth(par[i]);
}
vector<int> order;
int pre[100000];
void dfs2(int now){
pre[now] = order.size();
order.push_back(now);
for(int i=0; i<child[now].size(); i++){
dfs2(child[now][i]);
order.push_back(now);
}
}
SegmentTree st;
int lca(int a, int b){
//cout << a << " " << b << " " << pre[a] << " " << pre[b] << " " << st.minimum(pre[a], pre[b]+1) << endl;
a = pre[a];
b = pre[b];
if(a > b) swap(a,b);
return (int)(st.minimum(a, b+1));
}
int shouldChange[100000] = {};
int notChange[100000] = {};
int ans = 0;
int main(){
cin >> N >> M;
for(int i=0; i<M; i++){
int a,b;
cin >> a >> b;
a--; b--;
tonari[a].push_back(MP(b,i));
tonari[b].push_back(MP(a,i));
edge.push_back(MP(a,b));
}
for(int i=0; i<N; i++){
if(already[i]) continue;
already[i] = true;
par[c] = c;
dfs_order[i] = c;
c++;
dfs(i);
}
for(int i=0; i<M; i++){
if(ki[i]) continue;
other.push_back(MP(dfs_order[edge[i].first], dfs_order[edge[i].second]));
}
//for(int i=0; i<N; i++) cout << par[i] << endl;
//for(int i=0; i<other.size(); i++) cout << other[i].first << " " << other[i].second << endl;
//for(int i=0; i<N; i++){
// for(int j=0; j<child[i].size(); j++){
// cout << child[i][j] << " ";
// }
// cout << endl;
//}
//
int tmp = 0;
for(int i=0; i<other.size(); i++){
if(depth(other[i].first)%2 == depth(other[i].second)%2) tmp++;
}
if(tmp == 1) ans++;
//cout << tmp << endl;
//
for(int i=0; i<N; i++){
if(par[i] != i) continue;
dfs2(i);
}
//for(int i=0; i<order.size(); i++) cout << order[i] << (i==order.size()-1 ? "\n" : " ");
st.init(order.size());
for(int i=0; i<order.size(); i++) st.update(i, order[i]);
//
int count = 0;
for(int i=0; i<other.size(); i++){
//cout << other[i].first << " " << other[i].second << " " << lca(other[i].first, other[i].second) << endl;
if(depth(other[i].first)%2 == depth(other[i].second)%2){
count++;
shouldChange[other[i].first] += 1;
shouldChange[other[i].second] += 1;
shouldChange[lca(other[i].first, other[i].second)] -= 2;
}
else{
notChange[other[i].first] += 1;
notChange[other[i].second] += 1;
notChange[lca(other[i].first, other[i].second)] -= 2;
}
}
vector<pair<int,int> > d_i;
for(int i=0; i<N; i++){
d_i.push_back(MP(depth(i),i));
}
sort(d_i.begin(), d_i.end());
reverse(d_i.begin(), d_i.end());
for(int i=0; i<N; i++){
if(par[d_i[i].second] == d_i[i].second) continue;
shouldChange[par[d_i[i].second]] += shouldChange[d_i[i].second];
notChange[par[d_i[i].second]] += notChange[d_i[i].second];
}
//
for(int i=0; i<N; i++){
if(par[i] == i) continue;
//cout << notChange[i] << " " << shouldChange[i] << endl;
if(notChange[i] == 0 && shouldChange[i] == count) ans++;
}
//
cout << ans << endl;
return 0;
}
