Description

K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,CD,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊，规定任意一对相互认识的人不得在一队，国王相知道，最少可以分多少支队。

Input

第一行两个整数N，M。1<=N<=10000,1<=M<=1000000.表示有N个人，M对认识关系. 接下来M行每行输入一对朋友

Output

输出一个整数，最少可以分多少队

Sample Input

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

Sample Output

3

HINT

一种方案(1,3)(2)(4)

Source

这道题题意十分清晰。

就是用最少颜色给整个图染色使得相邻两个点之间的颜色不相同。

WC2009  cdq的讲稿中提到了这个问题：

http://wenku.baidu.com/link?url=gMlf2JA_ntdwxYgyTmd--5SjZJmy4UOmNqytRHB1KJer8JjQE2jgFCSOm5pH3rhArBnlA-d-ApYkeSI8JnEoHx0x6Diwuu1_NtAd0vtKwxu

还有一个问题   到现在依然没懂，望神犇解答

然而关于相关问题的证明，我们伟大的黄学长给了我一个博客。解释的十分清除：

http://ydcydcy1.blog.163.com/blog/static/21608904020142673343164/

那么当你看了两个东西之后相信就不用我这里再多说了。

#include <bits/stdc++.h>
#define N 10010
#define M 2000010
using namespace std;
int tot,n,m,d[N],vis[N],Hash[N],col[N],Q[N],head[N],next[M],v[M];
inline int max(int a, int b)
{
	if(a > b) return a;
	else return b;
}
void ins(int a,int b)
{
     v[++ tot] = b;
	 next[tot] = head[a];
	 head[a] = tot;
 }
 void insert(int a, int b)
 {
 	ins(a, b);
 	ins(b, a);
 }
int main()
{
    int a,b,ans;
    scanf("%d%d",&n,&m);
    tot = 0;
	memset(head,0,sizeof head);
    for (int i = 0; i < m; i ++)
	{
		scanf("%d%d",&a,&b);
		insert(a, b);
	}
    memset(vis,0,sizeof vis);
    memset(d,0,sizeof d);
    d[0] = -1;
    for (int i = n; i; i --)
    {
    	int j, k;
        for (k = 0, j = 1; j <= n; j ++)
        	if (!vis[j] && d[j] > d[k]) k = j;
        vis[k] = i;
		Q[i] = k;
        for (j = head[k]; j; j = next[j]) d[v[j]] ++;
    }
    memset(col,0,sizeof col);
    ans=0;
    for (int i = n; i; i --)
    {
    	int k = Q[i];
        for (int j = head[k]; j; j = next[j])
			Hash[col[v[j]]] = i;
        int j;
		for (j = 1; ; j ++) 
			if (Hash[j] != i)
				break;
        col[k] = j;
        ans = max(ans, j);
    }
    printf("%d\n",ans);
    return 0;
}