#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long T,a,b,c,d[1000001],v[1000001],o,h[1000001],fa[1000001],q,w,e,an,cn,st[1000001],u[1000001],de[1000001],rt,vi[1000001],si[1000001],cnn;
struct p{long long q,w;}l[1000001];
vector<int> qu[1000001],qu1[1000001],qu2[1000001],qu3[1000001];
void dfs(int qq,int ww)
{
	v[qq]=1;
	for(int i=0;i<qu[qq].size();i++)
	{
		if(qu[qq][i]!=ww)
		{
			if(!v[qu[qq][i]])
			{
				qu2[qq].push_back(qu[qq][i]);
				qu2[qu[qq][i]].push_back(qq);
				qu1[qq].push_back(qu[qq][i]);
				de[qu[qq][i]]=de[qq]+1;
				dfs(qu[qq][i],qq);
			}
		}
	}
}
void dfs2(int qq,int ww)
{
	vi[qq]=1;
	for(int i=0;i<qu1[qq].size();i++) dfs2(qu1[qq][i],qq);
}
void dfs1(int qq,int ww)
{
//	cout<<ww<<" "<<qq<<"\n";
	v[qq]=1;
	if(!ww)
	{
		for(int i=0;i<qu2[qq].size();i++)
		{
			if(!v[qu2[qq][i]]) qu3[qq].push_back(qu2[qq][i]),dfs1(qu2[qq][i],qq);
		}
	}
	else
	{
		if(vi[qq])
		{
			for(int i=0;i<qu2[qq].size();i++)
			{
				if(!v[qu2[qq][i]]) qu3[qq].push_back(qu2[qq][i]),dfs1(qu2[qq][i],qq); 
			}
			for(int i=0;i<qu[qq].size();i++)
			{
				if(!v[qu[qq][i]]&&!vi[qu[qq][i]]) qu3[qq].push_back(qu[qq][i]),dfs1(qu[qq][i],qq);
			}
		}
		else
		{
			for(int i=0;i<qu[qq].size();i++)
			{
				if(!v[qu[qq][i]]&&!vi[qu[qq][i]]) qu3[qq].push_back(qu[qq][i]),dfs1(qu[qq][i],qq);
			}
		}
	}
}
void dfs3(int qq)
{
	si[qq]=1;
	for(int i=0;i<qu3[qq].size();i++) dfs3(qu3[qq][i]),si[qq]+=si[qu3[qq][i]];
}
vector<int> tmp,ans[1000001];
void dfs4(int qq)
{
	for(int i=0;i<qu3[qq].size();i++)
	{
		tmp.clear();
		for(int j=0;j<a;j++)
		{
			if(j+1==qq||j+1==qu3[qq][i]) tmp.push_back(qq);
			else tmp.push_back(j+1);
		}
		ans[++cnn]=tmp;
		dfs4(qu3[qq][i]);
		tmp.clear();
		for(int j=0;j<a;j++)
		{
			if(j+1==qq||j+1==qu3[qq][i]) tmp.push_back(qq);
			else tmp.push_back(j+1);
		}
		ans[++cnn]=tmp;
	}
}
void work(int qq)
{
	tmp.clear();
	for(int i=0;i<a;i++) tmp.push_back(i+1);
	for(int i=0;i<qu3[qq].size();i++) tmp[qu3[qq][i]-1]=qq;
	ans[++cnn]=tmp;
}
int vv[1000001];
vector<p> tp;
void dfs5(int qq)
{
	for(int i=0;i<qu3[qq].size();i++)
	{
		if(d[qq]==0&&d[qu3[qq][i]]>0)
		{
			tp.push_back(p{qq,qu3[qq][i]});
		}
		dfs5(qu3[qq][i]);
	}
}
void get(int qq)
{
	while(d[qq]==0)
	{
		tmp.clear();
		for(int i=0;i<=a;i++) vv[i]=0;
		for(int i=1;i<=a;i++) tmp.push_back(i);
		tp.clear();
		dfs5(qq);
		for(int i=0;i<tp.size();i++)
		{
			if(!vv[tp[i].q]&&!vv[tp[i].w])
			{
				swap(d[tp[i].q],d[tp[i].w]);
				tmp[tp[i].w-1]=tp[i].q;
				vv[tp[i].q]=vv[tp[i].w]=1;
			}
		}
		ans[++cnn]=tmp;
	}
}
int main()
{
//	freopen("1.in","r",stdin);
	scanf("%lld%lld",&a,&b);
	for(int i=1;i<=b;i++)
	{
		scanf("%lld%lld",&q,&w);
		++q,++w;
		qu[q].push_back(w);
		qu[w].push_back(q);
	}
	dfs(1,0);
	long long mxx=0;
	for(int i=1;i<=a;i++) mxx=max(mxx,de[i]);
	if(mxx==a-1)
	{
		int tt=1;
		st[++cn]=tt;
		for(int i=1;i<a;i++)
		{
			tt=qu1[tt][0];
			st[++cn]=tt;
		}
		printf("%lld\n",a+1);
		for(int i=1;i<=a+1;i++)
		{
			if(i&1)
			{
				for(int j=1;j<=cn;j++)
				{
					d[st[j]]=(j+1)/2;
				}
			}
			else
			{
				for(int j=1;j<=cn;j++)
				{
					d[st[j]]=(j+2)/2;
				}
			}
			for(int j=1;j<=a;j++) printf("%lld ",d[j]);printf("\n");
		}
	}
	else
	{
		rt=1;
		for(int i=1;i<=a;i++)
		{
			if(qu1[i].size()>1)
			{
				rt=i;break;
			}
		}
		for(int i=1;i<=a;i++) v[i]=0;
		dfs2(rt,0);
//		for(int i=1;i<=a;i++) cout<<vi[i]<<" ";
		dfs1(rt,0);
		dfs3(rt);
		work(rt);
		cn=0;
		for(int i=0;i<qu3[rt].size();i++) st[++cn]=qu3[rt][i];st[cn+1]=st[1];
		for(int i=1;i<=a;i++) d[i]=i;
		for(int i=1;i<=cn;i++) d[st[i]]=0;
		for(int i=1;i<=cn;i++)
		{
			for(int j=1;j<si[st[i+1]];j++)
			{
				tmp.clear();
				for(int j=0;j<a;j++)
				{
					if(j+1==rt||j+1==st[i]) tmp.push_back(rt);
					else tmp.push_back(j+1);
				}
				ans[++cnn]=tmp;
				get(st[i+1]);
				work(rt);
				for(int k=1;k<=cn;k++) d[st[k]]=0;
			}
		}
		dfs4(rt);
		printf("%lld\n",cnn);
		for(int i=1;i<=cnn;i++)
		{
			for(int j=0;j<a;j++) printf("%lld ",ans[i][j]);
			printf("\n");
		}
	}
	return 0;
}