b.cpp

#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mk make_pair
using namespace std;

const int MAXN = 2000 + 5;
const int INF = 1e9 + 7;

vector <int> vec1, vec2, g[MAXN];
bool was[MAXN];
int mt[MAXN];
bool khun(int x){
    if (was[x])
        return false;
    was[x] = true;

    for (int i = 0; i < g[x].size(); i++){
        int to = g[x][i];
        if (mt[to] == -1 || khun(mt[to])){
            mt[to] = x;
            return true;
        }
    }
    return false;

}
int was2[MAXN];
void dfs(int x, int y){
    was2[x] = y;
    if (y == 1){
        vec1.pb(x);
    }
    else {
        vec2.pb(x);
    }

    for (int i = 0; i < g[x].size(); i++){
        if (!was2[g[x][i]]){
            dfs(g[x][i], 3 - y);
        }
        else if (was2[g[x][i]] == y){
            cout << "NO\n";
            exit(0);
        }
    }
}


int main() {
    IOS;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    for (int i = 1; i <= n; i++){
        if (!was2[i])
            dfs(i, 1);
    }

    for (int i = 0; i < vec2.size(); i++){
        mt[vec2[i]] = -1;
    }

    for (int i = 0; i < vec1.size(); i++){
        for (int j = 0; j < vec1.size(); j++){
            was[vec1[j]] = 0;
        }
        khun(vec1[i]);
    }
    int ans = 0;
    for (int i = 0; i < vec2.size(); i++){
        if (mt[vec2[i]] != -1){
            ans++;
            //cout << vec2[i] << ' ' << mt[vec2[i]] << '\n';
        }
    }
    cout << ans;

}