#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;
int a[5000][5000],n,m,t[5000][5000],viz[5000],viz1[5000],cont,linie;
vector<int>c[5000];
void dfs(int nod)
{

	int i,ok=0;
	for(i=1; i<=n && ok==0; i++)
		if(a[nod][i]==1) ok=1;
	if(ok==1)
	{
		viz[nod]=1;
		for(i=1;i<=n;i++)
		if(!viz[i]&&a[nod][i]==1)
			dfs(i);
	}

}


void dfst(int nod)
{

	int i,ok=0;
	for(i=1; i<=n && ok==0; i++)
		if(t[nod][i]==1) ok=1;
	if(ok==1)
	{viz1[nod]=1;
	for(i=1;i<=n;i++)
		if(!viz1[i] && t[nod][i]==1)
			dfst(i);
	}
}

int main()
{

	int i,j,x,y,ok=0;
	ifstream f("ctc.in");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		a[x][y]=1;
		t[y][x]=1;
		cont++;
	}
	cout<<endl;
	for(i=1; i<=n; i++)
		{for(j=1; j<=n; j++)
			cout<<a[i][j]<<" ";
			cout<<endl;}
		cout<<endl;
		for(i=1; i<=n; i++)
		{for(j=1; j<=n; j++)
			cout<<t[i][j]<<" ";
			cout<<endl;}
	f.close();
	cout<<cont<<endl;
	srand(time(0));
	int k;
	//while(cont!=0)
	{
		k=1+rand()%n;
		dfs(1);
		dfst(1);
	cout<<k<<endl;
	for(i=1; i<=n; i++) cout<<viz[i]<<" ";
	cout<<endl;
	for(i=1; i<=n; i++) cout<<viz1[i]<<" ";
	cout<<endl;
		for(i=1;i<=n;i++)
			if(viz[i]==1 && viz1[i]==1)
				{
					c[linie].push_back(i);
					ok=1;
			}
			/*for(i=0; i<c[linie].size(); i++)
				cout<<c[linie][i]<<" ";*/
			if(ok==1) {linie++; ok=0;}
			memset(viz,n,0);
			memset(viz1,n,0);
			for(i=0; i<c[linie-1].size(); i++)
				for(int j=1; j<=n; j++)
					if(a[c[linie-1][i]][j]==1)
					{
						a[c[linie-1][i]][j]=0;
						t[j][c[linie-1][i]]=0;
						cont--;
				}
					for(i=1; i<=n; i++)
		{for(j=1; j<=n; j++)
			cout<<a[i][j]<<" ";
			cout<<endl;}
		cout<<endl;
		for(i=1; i<=n; i++)
		{for(j=1; j<=n; j++)
			cout<<t[i][j]<<" ";
			cout<<endl;}
					
	}
	ofstream g("ctc.out");
	linie=linie-1;
	g<<linie<<"\n";
	for(i=0; i<linie; i++)
		{
			for(int j=0; j<c[i].size(); j++)
			g<<c[i][j]<<" ";
			g<<"\n";
	}
	g.close();
return 0;
}