#include<bits/stdc++.h>
using namespace std;
int a[105][105],n,m,x,y,maxx;
bool book[105],ans[105];
void dfs(int t,int sum){
	if(sum+n-t+1<=maxx) return ;
	if(t>n){
		if(sum>maxx){ 
			maxx=sum;
			for(int i=1;i<=n;i++) ans[i]=book[i]; 
		}
		return ;
	}
	if(book[t]==0){
		dfs(t+1,sum);
		return ; 
	} 
	int cnt=0,state[105];
	for(int i=1;i<=a[t][0];i++){
		if(book[a[t][i]]){
			state[++cnt]=a[t][i];  
			book[a[t][i]]=0;  
		}
	}
	dfs(t+1,sum+1); 
	for(int i=1;i<=cnt;i++) book[state[i]]=1;
	book[t]=0;
	dfs(t+1,sum);
	book[t]=1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		if(x<y) a[x][++a[x][0]]=y;
		else a[y][++a[y][0]]=x;
	}
	memset(book,1,sizeof book); 
	dfs(1,0);
	cout<<maxx<<endl;
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	} 
	return 0;
}