{$APPTYPE CONSOLE}
const maxn=102;
type qel=record
      i,j,t:longint;
     end;
     coord=record
      i,j:longint;
     end;
var p:array[1..maxn,1..maxn] of longint;
    d:array[1..maxn,1..maxn,1..3] of longint;
    q:array[1..maxn*maxn*3] of qel;
    nans,up,down,n,m,i0,j0,ix,jx:longint;
    ans:array[1..maxn*maxn*3] of coord;
    way:array[1..maxn,1..maxn,1..3] of qel;

procedure readdata;
var i,a,b:longint;
begin
 fillchar(p,sizeof(p),0);
 read(n,m,i0,j0,ix,jx);
 for i:=1 to m do
 begin
  read(a,b);
  p[a,b]:=1;
  p[b,a]:=1;
 end; 
end;

procedure addqueue(i,j,t,d0:longint);
begin
 if (d[i,j,t]=0) and (i<>j) and ((t<>1) or (p[i,j]=1)) then
  begin
   up:=up+1;
   q[up].i:=i;
   q[up].j:=j;
   q[up].t:=t;
   d[i,j,t]:=d0;
   way[i,j,t]:=q[down];
  end;
end;

procedure solve;
var i,j,t,i1,j1:longint;
    tw:qel;
begin
 fillchar(d,sizeof(d),0);
 down:=1;
 up:=0;
 addqueue(ix,jx,1,1);
 while up>=down do
 begin
  i:=q[down].i;
  j:=q[down].j;
  t:=q[down].t;
  if t=3 then
   for i1:=1 to n do
   if (p[i,i1]=1) and (i1<>j) then
    addqueue(i1,j,1,d[i,j,t]+1);
  if t=2 then
   for j1:=1 to n do
   if (p[j,j1]=1) and (j1<>i) then
    addqueue(i,j1,1,d[i,j,t]+1);
  if t=1 then
  begin
   for i1:=1 to n do
   if (p[i,i1]=1) and (i1<>j) then
   begin
    addqueue(i1,j,2,d[i,j,t]+1);
    if p[i1,j]=1 then
     addqueue(i1,j,1,d[i,j,t]+1);
   end;
   for j1:=1 to n do
   if (p[j,j1]=1) and (j1<>i) then
   begin
    addqueue(i,j1,3,d[i,j,t]+1);
    if p[i,j1]=1 then
     addqueue(i,j1,1,d[i,j,t]+1);
   end;
  end;
  down:=down+1;
 end;
 i:=i0;
 j:=j0;
 t:=1;
 nans:=0;
 while true do
 begin
  if t=1 then
  begin
   nans:=nans+1;
   ans[nans].i:=i;
   ans[nans].j:=j;
  end;
  if (i=ix) and (j=jx) then
   exit; 
  tw:=way[i,j,t];
  i:=tw.i;
  j:=tw.j;
  t:=tw.t;
 end;
end;

procedure outdata;
var i:longint;
begin
 writeln(d[i0,j0,1]-1,' ',nans);
 for i:=1 to nans do
 writeln(ans[i].i,' ',ans[i].j);
end;

begin
 assign(input,'kingdom.in');
 reset(input);
 assign(output,'kingdom.out');
 rewrite(output);
 readdata;
 solve;
 outdata;
 close(output);
end.
