var hp:array[0..2] of integer;             {počty hran s ohodnocením 0..2}
    hx:array[0..2,1..2*M*N] of integer;    {počáteční souřadnice}
    hy:array[0..2,1..2*M*N] of integer;
   hxo:array[0..2,1..2*M*N] of integer;    {cílové souřadnice}
   hyo:array[0..2,1..2*M*N] of integer;
     f:array[1..M,1..N] of boolean;        {značky navštívení}
    fv:array[1..M,1..N] of boolean;        {je kanálek z [i,j] doprava už vyroben}
    fs:array[1..M,1..N] of boolean;        {je kanálek z [i,j] dolů už vyroben}

procedure pridej(xo,yo,x,y:integer);       {přidá do haldy hranu odkud-kam}
var v:integer;
begin
  if xo>x and fv[x,y] then v:=0            {zjistím cenu}
    else if xo<x and fv[xo,y] then v:=0
      else if yo>y and fs[x,y] then v:=0
        else if yo<y and fs[x,yo] then v:=0
	  else if yo!=y then v:=1
	    else v:=2;
  inc(hp[v]);
  hx[v,hp[v]]:=x;
  hy[v,hp[v]]:=y;
  hxo[v,hp[v]]:=xo;
  hyo[v,hp[v]]:=yo;
end;
  
begin
  {nactu uz hotové do fv,fs}
   
  for i:=0 to N do
     for j:=1 to M do
      f[i,j]:=false;
  hp[0]:=1;
  hp[1]:=0;   hp[2]:=0;
  hx[0,1]=1; hy[0,1]:=1;
  while (hp[0]>0) or (hp[1]>0) or (hp[2]>0) do
  begin
    if hp[0]>0 then                         {vyberu hranu z haldy}
    begin 
      x:=hx[0,hp[0]]; y:=hy[0,hp[0]]; 
      xo:=hx[0,hp[0]]; yo:=hy[0,hp[0]]; dec(hp[0]);
    end else
      if hp[1]>0 then 
      begin 
        x:=hx[1,hp[1]]; y:=hy[1,hp[1]]; 
        xo:=hx[1,hp[1]]; yo:=hy[1,hp[1]]; dec(hp[1]);
      end else
        begin 
          x:=hx[2,hp[2]]; y:=hy[2,hp[2]]; 
          xo:=hx[2,hp[2]]; yo:=hy[2,hp[2]]; dec(hp[2]);
        end;
    if(not f[x,y])
    begin                                   {přidám [x,y] do kostry?}
      f[x,y]:=true;
      writeln("(",x,",",y,")-(",xo,",",yo,")");
      if y>1 then pridej(x,y,x,y-1);
      if x>1 then pridej(x,y,x-1,y);
      if y<N then pridej(x,y,x,y+1);
      if x<M then pridej(x,y,x+1,y);
    end;
  end;
end.