#include<bits/stdc++.h>
using namespace std;
int n,m,a[105][105],ans=-1;
string g,k;
int che(string h,int e){
	for(int i=0;i<h.size();i++){
		if(h[i]=='1'&&a[i+1][e]==1){
			return 0;
		}
	}
	return 1;
}
void dfs(int d,string s){
	if(d==n){
		int c=0;
		for(int i=0;i<s.size();i++){
			if(s[i]=='1'){
				c++;
			}
		}
		int o;
		if(che(s,d)==0){
			o=c;
			if(ans<o){
				g=s;
				ans=o;
			}
		}
		else{
			o=c+1;
			if(ans<o){
				g=s+"1";
				ans=o;
			}
		}
		return;
	}
	if(che(s,d)==1){
		dfs(d+1,s+"1");
	}
	dfs(d+1,s+"0");
}
int main(){
	int u,v;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		a[u][v]=1;
		a[v][u]=1;
	}
	dfs(1,k);
	cout<<ans<<endl;
	for(int i=0;i<g.size();i++){
		cout<<g[i]<<" ";
	} 
}
/*
7  10
1  2
1  4
2  4
2  3
2  5
2  6
3  5
3  6
4  5
5  6
*/ 

32分求助大佬