#include <bits/stdc++.h>
 
using namespace std;
 
int find(vector<int>& d, int a) {
    if(d[a] < 0) return a;
    return d[a] = find(d, d[a]);
}
 
void join(vector<int>& d, int a, int b) {
    a = find(d, a);
    b = find(d, b);
    if(a == b) return;
    d[a] += d[b];
    d[b] = a;
}
 
int main() {
    int n, m;
    cin >> n >> m;
 
    vector<vector<int>> adj(n);
    vector<int> d(n, -1);
    vector<pair<int,int>> edges;
 
    for(int i = 0; i < m; i++) {
        int n1, n2;
        cin >> n1 >> n2;
        n1--; n2--;
 
        adj[n1].push_back(n2);
        adj[n2].push_back(n1);
        edges.push_back({n1,n2});
    }
 
    for(int i = 0; i < n; i++) {
        for(int j = 1; j < adj[i].size(); j++) {
            join(d, adj[i][j-1], adj[i][j]);
        }
    }
 
    bool odd = false;
    for(int i = 0; i < n; i++) {
        if(d[i] < 0) {
            for(auto j : adj[i]) {
                if(find(d,i) == find(d,j)) {
                    odd = true;
                }
            }
        }
    }
 
    for(auto i : edges) {
        join(d,i.first,i.second);
    }
 
    int components = 0;
    for(int i = 0; i < n; i++) {
        if(d[i] < 0) components++;
    }
 
    components--;
    if(!odd) components++;
 
    cout << components << endl;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IGZpbmQodmVjdG9yPGludD4mIGQsIGludCBhKSB7CiAgICBpZihkW2FdIDwgMCkgcmV0dXJuIGE7CiAgICByZXR1cm4gZFthXSA9IGZpbmQoZCwgZFthXSk7Cn0KCnZvaWQgam9pbih2ZWN0b3I8aW50PiYgZCwgaW50IGEsIGludCBiKSB7CiAgICBhID0gZmluZChkLCBhKTsKICAgIGIgPSBmaW5kKGQsIGIpOwogICAgaWYoYSA9PSBiKSByZXR1cm47CiAgICBkW2FdICs9IGRbYl07CiAgICBkW2JdID0gYTsKfQoKaW50IG1haW4oKSB7CiAgICBpbnQgbiwgbTsKICAgIGNpbiA+PiBuID4+IG07CgogICAgdmVjdG9yPHZlY3RvcjxpbnQ+PiBhZGoobik7CiAgICB2ZWN0b3I8aW50PiBkKG4sIC0xKTsKICAgIHZlY3RvcjxwYWlyPGludCxpbnQ+PiBlZGdlczsKCiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbTsgaSsrKSB7CiAgICAgICAgaW50IG4xLCBuMjsKICAgICAgICBjaW4gPj4gbjEgPj4gbjI7CiAgICAgICAgbjEtLTsgbjItLTsKCiAgICAgICAgYWRqW24xXS5wdXNoX2JhY2sobjIpOwogICAgICAgIGFkaltuMl0ucHVzaF9iYWNrKG4xKTsKICAgICAgICBlZGdlcy5wdXNoX2JhY2soe24xLG4yfSk7CiAgICB9CgogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIGZvcihpbnQgaiA9IDE7IGogPCBhZGpbaV0uc2l6ZSgpOyBqKyspIHsKICAgICAgICAgICAgam9pbihkLCBhZGpbaV1bai0xXSwgYWRqW2ldW2pdKTsKICAgICAgICB9CiAgICB9CgogICAgYm9vbCBvZGQgPSBmYWxzZTsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICBpZihkW2ldIDwgMCkgewogICAgICAgICAgICBmb3IoYXV0byBqIDogYWRqW2ldKSB7CiAgICAgICAgICAgICAgICBpZihmaW5kKGQsaSkgPT0gZmluZChkLGopKSB7CiAgICAgICAgICAgICAgICAgICAgb2RkID0gdHJ1ZTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICBmb3IoYXV0byBpIDogZWRnZXMpIHsKICAgICAgICBqb2luKGQsaS5maXJzdCxpLnNlY29uZCk7CiAgICB9CgogICAgaW50IGNvbXBvbmVudHMgPSAwOwogICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIGlmKGRbaV0gPCAwKSBjb21wb25lbnRzKys7CiAgICB9CgogICAgY29tcG9uZW50cy0tOwogICAgaWYoIW9kZCkgY29tcG9uZW50cysrOwoKICAgIGNvdXQgPDwgY29tcG9uZW50cyA8PCBlbmRsOwp9

NSAxMAoxIDIKMiAzCjMgNAo0IDUKNSAxCjEgMwoyIDQKMyA1CjQgMQo1IDI=

5 10
1 2
2 3
3 4
4 5
5 1
1 3
2 4
3 5
4 1
5 2