#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
int p[200005];
int sl[200005];
bool cz[200005],vis[200005];
vector<int>v[200005];
vector<int>yy[405],qs[405];
int fa[200005];
int findf(int n)
{
	if(fa[n]==n)return n;
	return fa[n]=findf(fa[n]);
}
int xl1[200005],cnt1;
int xl2[200005],cnt2;
bool visd[200005];
int n,m;
void dfs(int x)
{
	if(visd[x])return;
	visd[x]=true;
	vector<int>v1;
	for(int i=1;i<=n;i++)
	{
		v1.clear();
		for(int j=0;j<yy[i].size();j++)
		{
			if(yy[i][j]==x)v1.push_back(j);
		}
		for(int j=0;j<qs[i].size();j++)
		{
			if(qs[i][j]==0)continue;
			if(!visd[qs[i][j]]&&!v1.empty())
			{
				//printf("%d %d\n",x,qs[i][j]);
				v[x].push_back(qs[i][j]);
				int sth=qs[i][j];
				yy[i][v1[v1.size()-1]]=0;
				qs[i][j]=0;
				v1.pop_back();
				dfs(sth);
			}
		}
	}
}
vector<int>wz[200005];
int now[1000005];
int sta[1000005],ttop;
void dfs1(int x)
{
	for(int i=now[x];i<v[x].size();i=now[x])
	{
		now[x]=i+1;
		dfs1(v[x][i]);
	}
	sta[++ttop]=x;
}
int main()
{
	n=read();
	m=read();
	for(int i=1;i<=n*m;i++)
	{
		p[i]=read();
	}
	for(int i=1;i<=m;i++)fa[i]=i;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)sl[j]=0;
		for(int j=1;j<=m;j++)
		{
			sl[p[(i-1)*m+j]]++;
			if(sl[p[(i-1)*m+j]]>=2)
			{
				cz[p[(i-1)*m+j]]=true;
				qs[i].push_back(p[(i-1)*m+j]);
				wz[p[(i-1)*m+j]].push_back((i-1)*m+j);
			}
		}
		for(int j=1;j<=m;j++)if(sl[j]==0)yy[i].push_back(j);
		if(!yy[i].empty())
		{
			for(int j=1;j<yy[i].size();j++)fa[findf(yy[i][0])]=findf(yy[i][j]);
			for(int j=0;j<qs[i].size();j++)fa[findf(yy[i][0])]=findf(qs[i][j]);
		}
	} 
	for(int j=1;j<=m;j++)
	{
		if(cz[j]==false)continue;
		if(findf(j)==j)
		{
			v[m+1].push_back(j);
			v[j].push_back(m+1);
			dfs(j);
		}
	}
	for(int i=1;i<=n;i++)
	{
		cnt1=cnt2=0;
		for(int j=0;j<yy[i].size();j++)
		{
			if(yy[i][j]!=0)xl1[++cnt1]=yy[i][j];
		}
		for(int j=0;j<qs[i].size();j++)
		{
			if(qs[i][j]!=0)xl2[++cnt2]=qs[i][j];
		}
		for(int j=1;j<=cnt1;j++)
		{
			v[xl1[j]].push_back(xl2[j]);
		}
	}
	dfs1(m+1);
	reverse(sta+1,sta+ttop+1);
	for(int i=1;i<=ttop;i++)printf("%d ",sta[i]);
	printf("\n");
	for(int i=1;i<=ttop;i++)
	{
		if(sta[i]==m+1)sta[i]=n*m+1;
		else
		{
			if(wz[sta[i]].empty())
			{
				sta[i]=0;
				continue;
			}
			int sth=sta[i];
			sta[i]=wz[sth][wz[sth].size()-1];
			wz[sth].pop_back();
		}
	}
	for(int i=1;i<=ttop;i++)printf("%d ",sta[i]);
	printf("\n");
	cnt1=0;
	for(int i=1;i<=ttop;i++)if(sta[i]!=0)sta[++cnt1]=sta[i];
	printf("%d\n",cnt1-1);
	for(int i=cnt1;i>=2;i--)printf("%d %d\n",sta[i-1],sta[i]);
	return 0;
}