#include<bits/stdc++.h>
using namespace std;
int n;
int const N=1100;
int mapp[N][N]={};//敌人 
int listpd[N]={};//所用 
int largestlist[N]={};//最终 
int largest=-1;//最终数量 
int pd=0;
void updata(int sum)
{
	if(sum>largest)
	{
		largest=sum;
		for(int i=1;i<=n;i++)
			largestlist[i]=listpd[i];
	}
}
void finding(int k,int sum)
{
	if(k>n)
		updata(sum);
	else
	{
		pd=0;
		for(int i=1;i<=n;i++)
		{
			if(listpd[i]==1&&mapp[i][k]==1)
			{
				pd=1;
				break;
			}
		}
		if(sum+(n-k+1)<=largest)	return;
		if(pd)	finding(k+1,sum);
		else
		{
			listpd[k]=1;
			finding(k+1,sum+1);
			listpd[k]=0;
		}
	}
}
int main()
{
	int m;
	scanf("%d%d",&n,&m);
	int a1,a2;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&a1,&a2);
		mapp[a1][a2]=1;
		mapp[a2][a1]=1;
	}
	for(int i=1;i<=n;i++)	finding(i,0);
	
	printf("%d\n",largest);
	for(int i=1;i<=n;i++)
		printf("%d ",largestlist[i]);
	return 0;
}