#include <bits/stdc++.h>
using namespace std;
int n,m,cnt1,cnt2,flag,c=1,mapp[600][600],book[600][600],book2[600],d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct node
{
	int s,e;
}a[600],last;
bool cmp(node x,node y)
{
	return x.e>y.e;
}
void dfs(int x,int y)
{
	book[x][y]=1;
	if(x==n)
	{
		book2[y]=1;
		a[y].s=min(y,a[y].s);
		a[y].e=max(y,a[y].e); 
	}
	for(int i=0;i<4;i++)
	{
		int nx=x+d[i][0],ny=y+d[i][1];
		if(nx<1||nx>n||ny<1||ny>m)continue;
		if(mapp[nx][ny]<mapp[x][y]&&book[nx][ny]==0)
		{
			book[nx][ny]=0;
			dfs(nx,ny);
			book[nx][ny]=1;
		}
	}
}
int main()
{
	for(int i=0;i<600;i++)
	{
		a[i].s=600;
		a[i].e=0; 
	}
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>mapp[i][j];
		}
	}
	for(int i=1;i<=m;i++)
	{
		memset(book,0,sizeof(book));
		dfs(1,i);
	}
	for(int i=1;i<=m;i++)
	{
		cout<<a[i].s <<" "<<a[i].e<<endl;
	}
	sort(a+1,a+m+1,cmp);
	while(last.e<m)
	{  
		flag=0;
		for(int i=1;i<=m;i++)
		{
			if(a[i].s>=last.s+1&&a[i].s<=last.e+1)
			{
				last=a[i];
				cnt1++;
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
			c=0;
			cnt2++;
		}	
	}
	if(c==1)cout<<1<<endl<<cnt1;
	else  cout<<0<<endl<<cnt2;
	return 0;
}