cf 167.div2 E.Dima and Horses

    题意很简单，就是分组，让冲突最多有一种，因为只要分成2组，就是个2-SAT

    但是最多只有3个不和，就是不和的三个里至少有2个在一组，所以应该必然有解（这边不太明白，感觉这样），直接染色就可以了

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int en[300010][3];
int d[300010];
bool ok[300010];
bool sat(int v)
{
    int i,now=0,u;
    for(i=0;i<d[v];i++)
    {
        u=en[v][i];
        if(ok[u]==ok[v])now++;
    }
    if(now>1)
    {
        ok[v]=!ok[v];
        for(i=0;i<d[v];i++)
        {
            u=en[v][i];
            if(ok[v]==ok[u])sat(u);
        }
    }
}
int main()
{
    int n,m,i,a,b;
    scanf("%d%d",&n,&m);
    memset(d,0,sizeof(d));
    memset(ok,0,sizeof(ok));
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&a,&b);
        en[a][d[a]++]=b;
        en[b][d[b]++]=a;
    }
    for(i=1;i<=n;i++)
      sat(i);
    for(i=1;i<=n;i++)
      printf("%d",ok[i]);
    puts("");
}