#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

using ll = long long;
const int N = 1e5 + 5;

vector<int> edges[N];
int color[N];

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].emplace_back(v);
        edges[v].emplace_back(u);
    }

    function<int(int, int, int)> dfs = [&](int u, int fa, int col) -> int {
        int ans = 0;
        color[u] = col;
        for (int v : edges[u]) {
            if (v == fa)
                continue;
            ans ^= (dfs(v, u, col) + 1);
        }
        return ans == 0 ? 1 : ans;
    };

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (color[i])
            continue;
        ans ^= dfs(i, 0, i);
    }
    cout << (ans - 1 >= 0 ? ans - 1 : 0) << endl;

    return 0;
}