RT,30分，自测没问题

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n,m,i,l[200005],r[200005];
bool vis[100005]={};
inline int in(){
	int x=0;char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}
inline void swapx(bool &a,bool &b){
	int t=a;
	a=b;
	b=t;
}
int main(){
	freopen("cut.in","r",stdin);
	freopen("cut.out","w",stdout);
	srand(0);
	n=in(),m=in();
	for(i=1;i<=m;++i)l[i]=in(),r[i]=in();
	for(i=1;i<=(n>>1);++i)vis[i]=1;
	while(1){
		srand(rand()*32768+rand());
		for(i=1;i<=n;++i)swapx(vis[i],vis[(rand()*32767+rand())%n+1]);
		int t=0;
		for(i=1;i<=m;++i)if(vis[l[i]]^vis[r[i]])++t;
		if((t<<1)>=m){
			for(i=1;i<=n;++i)printf("%d ",vis[i]);
			return 0;
		}
	}
}

违规紫衫