program aa;
var
e:array[1..501,1..501] of longint;
a,b,c,d:array[1..500] of longint;
f:array[1..500] of boolean;
v:array[1..500] of integer;
i,j,k,n,m,x:longint;
sum,max,min:longint;
procedure sort(i,j:integer);
var
x,l,r,t:integer;
begin
l:=i;
r:=j;
x:=(l+r) div 2;
repeat
while a[l]<a[x] do inc(l);
while a[r]>a[x] do dec(r);
if l<=r then begin
t:=a[l];
a[l]:=a[r];
a[r]:=t;
t:=b[l];
b[l]:=b[r];
b[r]:=t;
inc(l);
dec(r);
end;
until l>r;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure bfs(i,j:integer);
begin
if (i<=0) or (i>n) or (j<=0) or (j>m) then exit;
if i=n then
begin
if not f[j] then
begin
f[j]:=true; inc(sum);
end;
if j<min then min:=j;
if j>max then max:=j;
end;
if e[i-1,j]<e[i,j] then bfs(i-1,j);
if e[i,j-1]<e[i,j] then bfs(i,j-1);
if e[i+1,j]<e[i,j] then bfs(i+1,j);
if e[i,j+1]<e[i,j] then bfs(i,j+1);
end;
begin
fillchar(f,sizeof(f),false);
readln(n,m);
for i:=1 to n do
for j:=1 to m do
read(e[i,j]);
sum:=0;
for i:=1 to m do
begin
min:=501;
max:=0;
bfs(1,i);
if min<>501 then
a[i]:=min;
k:=i;
b[i]:=max;
if sum=m then break;
end;
if sum<m then begin writeln(0);writeln(m-sum);exit;end;
sort(1,k);
i:=1;
while a[i]=0 do
inc(i);
fillchar(v,sizeof(v),$1b);
v[0]:=0;
for j:=i to k do
for x:=a[j] to b[j] do
if v[a[j]-1]+1<v[x] then v[x]:=v[a[j]-1]+1;
writeln(1);
writeln(v[m]);
end.
program water;
var i,j,k,n,m,cannot,l,r:longint;
flag:boolean;
h:array[0..600,0..600]of longint;
v:array[0..600,0..600]of boolean;
flow:array[0..1000,0..2]of longint;
f:array[0..1000]of longint;
procedure floodfill(x,y:longint);
begin
if v[x,y] then exit;
v[x,y]:=true;
if h[x-1,y]<h[x,y] then floodfill(x-1,y);
if h[x+1,y]<h[x,y] then floodfill(x+1,y);
if h[x,y-1]<h[x,y] then floodfill(x,y-1);
if h[x,y+1]<h[x,y] then floodfill(x,y+1);
end;
procedure swap(var a,b:longint);
var t:longint;
begin
t:=a;a:=b;b:=t;
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
begin
readln(n,m);
fillchar(h,sizeof(h),127);
for i:=1 to n do
for j:=1 to m do
read(h[i,j]);
fillchar(v,sizeof(v),false);
for i:=1 to m do floodfill(1,i);
cannot:=0;
for i:=1 to m do
if not v[n,i] then inc(cannot);
if cannot<>0 then
begin
writeln(0);writeln(cannot);halt;
end;
writeln(1);
k:=0;
for i:=1 to m do
begin
fillchar(v,sizeof(v),false);
floodfill(1,i);
l:=0;r:=m+1;flag:=true;
while (l<=r)and(flag) do
begin
flag:=false;
if not v[n,l] then begin
inc(l);flag:=true;
end;
if not v[n,r] then begin
dec(r);flag:=true;
end;
end;
if l>r then continue;
inc(k);flow[k,1]:=l;flow[k,2]:=r;
end;
for i:=1 to k-1 do
for j:=i+1 to k do
if flow[i,1]>flow[j,1] then
begin
swap(flow[i,1],flow[j,1]);
swap(flow[i,2],flow[j,2]);
end;
fillchar(f,sizeof(f),127);f[0]:=0;
for i:=1 to k do
for j:=flow[i,1] to flow[i,2] do
f[j]:=min(f[j],f[flow[i,1]-1]+1);
writeln(f[m]);
end.