#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=1010;
const int M=50010;
int head[N];
int next_[M<<1];
int goal[M<<1];
int cnt_e=0;


int n,m;
int match[N];
int fa[N];
int type[N];
int pre[N];
int q[N],l,r;


void add(int a,int b,int e)
{
	next_[e]=head[a];
	head[a]=e;
	goal[e]=b;
	return;
}
void swap(int &a,int &b)
{
	int k=a; a=b; b=k;
}
int find(int x)
{
	int k=x,i;
	while(fa[k]!=k)k=fa[k];
	while(fa[x]!=k)
	{
		i=fa[x]; fa[x]=k; x=i;
	}
	return k;
}

int vis[N],cnt=0;
int lca(int a,int b)
{
	int k,i,j;
	cnt++;
	a=find(a); b=find(b);
	while(vis[a]!=cnt)
	{
		vis[a]=cnt;
		a=find(pre[match[a]]);
		if(b)swap(a,b);
	}
	return a;
}
void shrink(int x,int root)
{
	int k,i,j;
	x=find(x);
	while(x!=root)
	{
		k=pre[match[x]];
		if(type[match[x]]==2)
		{
			type[match[x]]=1;
			q[++r]=match[x];
		}
		if(find(k)!=root)pre[k]=match[x];
		fa[x]=root; fa[find(match[x])]=root;
		x=find(k);
	}
	return;
}
void bfs(int x)
{
	int k,i,j;
	int a,b,c;
	for(k=1;k<=n;k++)type[k]=vis[k]=pre[k]=0;
	cnt=0; 
	for(k=1;k<=n;k++)fa[k]=k;
	type[x]=1; pre[x]=0;
	l=0; r=-1;
	q[++r]=x;
	while(l<=r)
	{
		a=q[l]; l++;
		for(i=head[a];i!=-1;i=next_[i])
		{
			k=goal[i];
			if(!type[k])
			{
				if(!match[k])
				{
					pre[k]=a;
					while(k)
					{
						i=match[pre[k]];
						match[k]=pre[k]; match[pre[k]]=k;
						k=i;
					}
					return;
				}
				type[k]=2;
				type[match[k]]=1;
				pre[k]=a;
				q[++r]=match[k];
			}
			else if(type[k]==1 && k!=match[a] && find(a)!=find(k))
			{
				b=k;
				c=lca(a,b);
				if(find(a)!=c)pre[a]=b;
				if(find(b)!=c)pre[b]=a;
				shrink(a,c);
				shrink(b,c);
			}
			
		}
	}
	return;
}
void blossom()
{
	int k,i,j;
	for(k=1;k<=n;k++)match[k]=0;
	for(k=1;k<=n;k++)
	{
		if(!match[k])
		{
			bfs(k);
		}
	}
	return;
}
int main()
{
	int k,i,j;
	int a,b,c;
	int sum=0;
	memset(head,-1,sizeof(head));
	scanf("%d%d",&n,&m);
	for(k=0;k<m;k++)
	{
		scanf("%d%d",&a,&b);
		add(a,b,cnt_e++);
		add(b,a,cnt_e++);
	}
	
	blossom();
	
	for(k=1;k<=n;k++)if(match[k])sum++;
	printf("%d\n",sum/2);
	for(k=1;k<=n;k++)printf("%d ",match[k]);
	printf("\n");
	
	return 0;
}