题解：

假设图联通，那么由于每次走两步，相当于在规定一个起点后只能走奇偶性相同的点，所以，对于每一个连通块，我们只需要01染色后，看一下有没有相同颜色连边的情况，如果有，那就说明奇偶性不同的点能够到达，也就是说，我们可以遍历整张图，如果没有，那么我们直接加一条即可，
然后如果图不连通，那么首先，我们最少要多加连通块-1条边，然后如果这些连通块中有一个出现相同颜色边的情况，那么我们的只有把图联通即可，否则，则需多加一条

代码

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;

int main(){
    //freopen("a.in", "r", stdin);

    int n,m,col[100010],vis[100010],flag=1;
    vector<int> G[100010];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        int u,v;scanf("%d%d",&u,&v);
        G[u].pb(v);G[v].pb(u);
    }

    function<void(int ,int)> dfs = [&] (int u,int cl) {
        col[u]=cl;vis[u]=1;
        for(int v:G[u]) {
            if(col[v]) {
                if(col[v]==cl) flag=0;
            }
            else dfs(v,3-cl);
        }
    };
    int t=0;

    for(int i=1;i<=n;i++) {
        if(!vis[i]) {
            dfs(i,1);
            t++;
        }
    }
    printf("%d\n",t-1+flag);

    return 0;
}

/*
8 8
1 2
2 3
3 4
4 2
5 6
6 7
7 8
8 6
*/