solution

我们从1号点开始染色，标记为0的点表示可以从1号点走偶数步到达，标记为1的点表示可以从1号点走奇数步到达。最后就是想要所有点都可以标记为0。如果存在一个奇环，那么这个环上的点既可以标记为1，也可以标记为0，所以所有与这个奇环相连的点都可以标记为0和1。

所以我们只要保证最终连接成一个包含奇环的连通块就可以了，如果存在至少一个连通块里本来就有一个奇环，那么只要让其他连通块向其连边即可，答案就是(S表示连通块个数)。如果不存在一个连通块里有奇环，那么就要自己连出一个奇环，显然连出一个奇环只需要添加1条边，所以答案就是。

判断一个连通块内是不是存在奇环可以用二分图染色。如果无法进行二分图染色就表明该连通块内存在奇环。

code

/*
* @Author: wxyww
* @Date:   2020-05-20 13:54:52
* @Last Modified time: 2020-05-20 14:40:48
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
struct node {
    int v,nxt;
}e[N << 1];
int head[N],ejs;
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}

int vis[N],ANS = 1;

void dfs(int u,int fa) {
    vis[u] = vis[fa] + 1;
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;if(v == fa) continue;
        if(vis[v]) {
            if(!((vis[v] - vis[u]) & 1)) ANS = 0;
            continue;
        }
        dfs(v,u);
    }
    return;
}

int main() {

    int n = read(),m = read();
    for(int i = 1;i <= m;++i) {
        int u = read(),v = read();
        add(u,v);add(v,u);
    }
    int ans = 0;
    for(int i = 1;i <= n;++i) {
        if(vis[i]) continue;
        ans++;
        dfs(i,0);
    }
    cout<<ans - 1 + ANS;
    return 0;
}