#include <bits/stdc++.h>
using namespace std;
struct op {
int x;
int y;
int sx;
int sy;
int cx;
int cy;
bool b;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> u(m), v(m);
for (int i = 0; i < m; i++) {
cin >> u[i] >> v[i];
--u[i]; --v[i];
}
int ans = 0;
bool bip = true;
vector<int> f(n);
vector<int> sz(n, 1);
vector<int> col(n);
iota(f.begin(), f.end(), 0);
stack<op> stk;
function<int(int)> Get = [&](int x) {
return f[x] == x ? x : Get(f[x]);
};
function<int(int)> Col = [&](int x) {
return f[x] == x ? col[x] : col[x] ^ Col(f[x]);
};
auto Unite = [&](int x, int y) {
int px = Get(x);
int py = Get(y);
int cx = Col(x);
int cy = Col(y);
stk.push({px, py, sz[px], sz[py], col[px], col[py], bip});
if (px == py) {
if (cx == cy) {
bip = false;
}
return;
}
if (sz[px] < sz[py]) {
swap(px, py);
}
col[py] ^= col[px];
if (cx == cy) {
col[py] ^= 1;
}
f[py] = px;
sz[px] += sz[py];
};
auto Rollback = [&]() {
op o = stk.top();
stk.pop();
int x = o.x;
int y = o.y;
f[x] = x;
f[y] = y;
sz[x] = o.sx;
sz[y] = o.sy;
col[x] = o.cx;
col[y] = o.cy;
bip = o.b;
};
vector<vector<int>> qs(4 * m);
function<void(int, int, int, int, int, int)> AddEdge = [&](int x, int l, int r, int ql, int qr, int i) {
if (ql <= l && r <= qr) {
qs[x].push_back(i);
return;
}
int mid = (l + r) / 2;
if (qr <= mid) {
AddEdge(x << 1, l, mid, ql, qr, i);
} else if (ql > mid) {
AddEdge(x << 1 | 1, mid + 1, r, ql, qr, i);
} else {
AddEdge(x << 1, l, mid, ql, qr, i);
AddEdge(x << 1 | 1, mid + 1, r, ql, qr, i);
}
};
function<void(int, int, int)> Solve = [&](int x, int l, int r) {
for (int i : qs[x]) {
Unite(u[i], v[i]);
}
if (l == r) {
if (bip && (Get(u[l]) != Get(v[l]) || Col(u[l]) == Col(v[l]))) {
ans += 1;
}
for (int i : qs[x]) {
Rollback();
}
return;
}
int mid = (l + r) / 2;
Solve(x << 1, l, mid);
Solve(x << 1 | 1, mid + 1, r);
for (int i : qs[x]) {
Rollback();
}
};
for (int i = 0; i < m; i++) {
if (i > 0) {
AddEdge(1, 0, m - 1, 0, i - 1, i);
}
if (i + 1 < m) {
AddEdge(1, 0, m - 1, i + 1, m - 1, i);
}
}
Solve(1, 0, m - 1);
cout << ans << '\n';
return 0;
}
