There are a group of students. Some of them may know each other, while others don't. For example, A and B know each other, B and C know each other. But this may not imply that A and C know each other. 

Now you are given all pairs of students who know each other. Your task is to divide the students into two groups so that any two students in the same group don't know each other.If this goal can be achieved, then arrange them into double rooms. Remember, only paris appearing in the previous given set can live in the same room, which means only known students can live in the same room. 

Calculate the maximum number of pairs that can be arranged into these double rooms. 

Input

For each data set: 
The first line gives two integers, n and m(1<n<=200), indicating there are n students and m pairs of students who know each other. The next m lines give such pairs. 

Proceed to the end of file. 
 

Output

If these students cannot be divided into two groups, print "No". Otherwise, print the maximum number of pairs that can be arranged in those rooms. 

Sample Input

4 4
1 2
1 3
1 4
2 3
6 5
1 2
1 3
1 4
2 5
3 6

Sample Output

No
3

题目大意:有n个人,有m种认识关系, 但是a认识b,b认识c, a不一定认识c,问能否把这n个人分成两组,每组之内的人都不认识,之后两个认识的人住到一间屋,问最多可以分几间屋.

题目思路:

首先,搞清楚第一个问题,如何才能分成两组,两组之内人互相不认识,我们把图建立好后,这个图是认识的关系,所以相邻节点之间不能在一个屋,我们用染色法来对这个图进行判定,判定之后所有颜色相同的都不互相认识,因为认识关系不可传递.之后进行二分图最大匹配就是最后答案.

AC:

//#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=1e9+5;
const int maxn=2e6+8;
const double PI=acos(-1);
const ll mod=1e9+7;
ll n,m;
vector<ll>v[505];
int vis[205];
int save[205],cop[205];
bool used[505];
int girl[505];
ll cnt1=0,cnt2=0;
bool dfs(int u,int c)
{
    vis[u]=c;
    int sz=v[u].size();
    for(int i=0;i<sz;i++)
    {
        int e=v[u][i];
        if(vis[e]==c) return false;
        if(!vis[e]&&!dfs(e,-c)) return false;
    }
    return true;
}
bool AC(int x)
{
    int sz=v[x].size();
    for(int i=0;i<sz;i++)
    {
        if(!used[v[x][i]])
        {
            used[v[x][i]]=1;
            if(!girl[v[x][i]]||AC(girl[v[x][i]]))
            {
                girl[v[x][i]]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        memset(girl,0,sizeof(girl));
        for(int i=1;i<=n;i++)
            v[i].clear();
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        bool f;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
                 f=dfs(i,1);
        }
        if(!f) printf("No\n");
        else
        {
            cnt1=0;cnt2=0;
            for(int i=1;i<=n;i++)
                if(vis[i]==1) save[++cnt1]=i;
                else if(vis[i]==-1) cop[++cnt2]=i;
            ll sum=0;
            for(int i=1;i<=cnt1;i++)
            {
                memset(used,false,sizeof(used));
                if(AC(save[i])) sum++;
            }
            printf("%lld\n",sum);
        }
    }
    return 0;
}

总结:此题单独发博客关键是二分图的判定!