#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define fi first #define se second const int N = 4e6 + 5; int n, m, ans; int tot, dfn[N], low[N], tp, stk[N], ins[N], cnt, bel[N]; int vis[N], tag[N], sum, sum2; int fl[N]; vector<pii> v[N]; vector<int> g[N]; void trav(int x) { tag[x] = 1; //cout<<v[x].size()-2<<' '; if (v[x].size() & 1) sum++; if (v[x].size() > 2) sum2++; for (auto it : v[x]) { int y = it.se; if (!vis[y] || tag[y]) continue; trav(y); } } void dfs(int x, int lst) { dfn[x] = low[x] = ++tot; stk[++tp] = x, ins[x] = 1; for (auto it : v[x]) { int id = it.fi, y = it.se; if (id == lst) continue; if (!dfn[y]) { dfs(y, id); low[x] = min(low[x], low[y]); } else low[x] = min(low[x], dfn[y]); } if (dfn[x] == low[x]) { cnt++; vector<int> tmp; int id = 0; while (1) { int y = stk[tp--]; ins[y] = 1; bel[y] = cnt; tmp.push_back(y); if (v[y].size() > 2) id = y; vis[y] = 1; if (x == y) break; } if (tmp.size() == 1) { for (int y : tmp) vis[y] = 0, tag[y] = 0; return; } if (id) { sum = sum2 = 0; trav(id); if (sum == 1) ans++; else if (sum2 == 1) ans++; else ans += sum / 2; } else ans++; for (int y : tmp) vis[y] = 0, tag[y] = 0; } } void dfs2(int x, int fa) { fl[x] = 1; int son = 0; for (int y : g[x]) { if (y == fa) continue; son++; dfs2(y, x); } if (fa) ans += son / 2; else ans += (son + 1) / 2; } int main() { // freopen("data.in", "r", stdin); // freopen("my.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> m; for (int i = 1, x, y; i <= m; i++) { cin >> x >> y; v[x].push_back({i, y}); v[y].push_back({i, x}); } for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i, 0); for (int x = 1; x <= n; x++) { for (auto it : v[x]) { int y = it.se; if (bel[x] >= bel[y]) continue; g[bel[x]].push_back(bel[y]); g[bel[y]].push_back(bel[x]); } } // cout << ans << endl; for (int i = 1; i <= cnt; i++) if (!fl[i]) dfs2(i, 0); cout << ans; return 0; }