#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, col[100100], chk[200200];
vector<array<int, 2>> v[100100], odd, even;
int in[100100], out[100100], t[200200], cnt;
void dfs(int u, int p, int pid, int c) {
col[u] = c, in[u] = ++cnt;
for(auto [x, id] : v[u]) if(!chk[id]) {
chk[id] = 1;
if(col[x] == -1) {
dfs(x, u, id, c^1);
continue;
}
if(col[x] != c) even.push_back({u, x});
else odd.push_back({u, x});
}
out[u] = ++cnt;
}
void update(int b, int c) {
while(b <= 2*n) t[b] += c, b += b & -b;
}
int find(int b) {
int re = 0;
while(b) re += t[b], b -= b & -b;
return re;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=1;i<=m;i++) {
int x, y; cin >> x >> y;
v[x].push_back({y, i}), v[y].push_back({x, i});
}
memset(col, -1, sizeof col);
for(int i=1;i<=n;i++) if(!in[i]) dfs(i, 0, 0, 0), update(in[i], 3*m), update(in[i]+1, -3*m);
for(auto [x, y] : even) update(in[y]+1, -1), update(in[x]+1, 1);
for(auto [x, y] : odd) update(in[y]+1, 1), update(in[x]+1, -1);
int cnt = 0;
for(int i=2;i<=n;i++) if(find(in[i])-find(out[i]) == odd.size()) cnt++;
cout << cnt + (odd.size() == 1);
}
