1 #include <cstdio> 2 #include <cstring> 3  4 #define MAXN 205 5  6 char map[MAXN][MAXN]; 7 int link[MAXN]; 8 int color[MAXN]; 9 bool visit[MAXN];10 int n, m;11 12 bool dfs(int v, int col) {13     int i;14 15     for (i=1; i<=n; ++i) {16         if (map[i][v]) {17             if (color[i] == col)18                 return false;19             else if (color[i] == 0) {20                 color[i] = -col;21                 if (dfs(i, -col) == false)22                     return false;23             }24         }25     }26     return true;27 }28 29 bool find(int v) {30     int i;31 32     for (i=1; i<=n; ++i) {33         if (!visit[i] && map[i][v]) {34             visit[i] = true;35             if (link[i]==0 || find(link[i])) {36                 link[i] = v;37                 return true;38             }39         }40     }41     return false;42 }43 44 int main() {45     int ans;46     int i, j;47 48     while (scanf("%d%d", &n, &m) != EOF) {49         memset(map, 0, sizeof(map));50         memset(link, 0, sizeof(link));51         memset(color, 0, sizeof(color));52         while (m--) {53             scanf("%d %d", &i, &j);54             map[i][j] = map[j][i] = 1;55         }56         color[1] = 1;57         if (dfs(1, 1) == false) {58             printf("No\n");59             continue;60         }61         for (ans=0, i=1; i<=n; ++i) {62             memset(visit, false, sizeof(visit));63             if (find(i))64                 ++ans;65         }66         printf("%d\n", ans/2);67     }68 69     return 0;70 }