#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const int MAXL = 20;
int root[MAXN], cntNepar, valNepar[MAXN], valPar[MAXN], in[MAXN], out[MAXN], dist[MAXN], timer, sol;
vector<pair<int, int> > adj[MAXN], e;
bool pos[MAXN];
int anc[MAXN][MAXL];
set<int> s;
set<pair<int, int>> ss, dupl, sols;
void dfsRoot(int node, int pret, int rt) {
in[node] = ++timer;
root[node] = rt;
anc[node][0] = pret;
dist[node] = dist[pret]+1;
for (auto x : adj[node]) {
if (root[x.first] == 0) {
s.erase(x.second);
dfsRoot(x.first, node, rt);
}
}
out[node] = ++timer;
}
void dfsScore(int node) {
pos[node] = true;
for (auto x : adj[node]) {
if (!pos[x.first]) {
dfsScore(x.first);
valNepar[node] += valNepar[x.first];
valPar[node] += valPar[x.first];
}
}
//cerr << "UBACEN " << node << ' ' << anc[node][0] << ' ' << valPar[node] << ' ' << valNepar[node] << endl;
if (anc[node][0] != node && valNepar[node] == cntNepar && valPar[node] == 0) {
sols.insert({min(node, anc[node][0]), max(node, anc[node][0])});
}
}
bool inSubtree(int x, int y) { // x in subtree of y
return (in[y] <= in[x] && out[x] <= out[y]);
}
int LCA(int x, int y) {
if (inSubtree(x, y)) {
return y;
}
if (inSubtree(y, x)) {
return x;
}
for (int l = MAXL-1; l >= 0; l--) {
if (!inSubtree(y, anc[x][l])) {
x = anc[x][l];
}
//cerr << "LCASTEP " << x << ' ' << l << endl;
}
return anc[x][0];
}
bool odd(int x, int y, int lca) {
return (dist[x]+dist[y])%2 == 0;
}
int main() {
ios::sync_with_stdio(false);
int n, m; cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y; cin >> x >> y;
adj[x].push_back({y, i-1});
adj[y].push_back({x, i-1});
e.push_back({x, y});
s.insert(i-1);
if (ss.find({min(x, y), max(x, y)}) != ss.end()) {
dupl.insert({min(x, y), max(x, y)});
}
ss.insert({min(x, y), max(x, y)});
}
for (int i = 1; i <= n; i++) {
if (root[i] == 0) {
dfsRoot(i, i, i);
}
//cerr << "PARENT " << i << ' ' << anc[i][0] << endl;
}
for (int l = 1; l < MAXL; l++) {
for (int i = 1; i <= n; i++) {
anc[i][l] = anc[anc[i][l-1]][l-1];
}
}
for (auto p : s) {
int x = e[p].first, y = e[p].second;
int lca = LCA(x, y);
//cerr << "LCA " << x << ' ' << y << ' ' << lca << endl;
if (odd(x, y, lca)) {
valNepar[lca] -= 2;
valNepar[x] += 1;
valNepar[y] += 1;
cntNepar += 1;
} else {
valPar[lca] -= 2;
valPar[x] += 1;
valPar[y] += 1;
}
}
for (int i = 1; i <= n; i++) {
if (!pos[i]) {
dfsScore(i);
}
}
for (auto x : dupl) {
if (sols.find(x) != sols.end()) {
sols.erase(x);
}
}
sol = sols.size();
if (cntNepar == 1) {
sol++;
}
cout << sol;
return 0;
}
