program taskk2;

{$APPTYPE CONSOLE}

uses
  SysUtils;
var
a:array[1..100,0..100] of integer;
i,X,Y,j,N,M,Sx,sy,fx,fy:integer;
Vis:array[1..100,1..100] of integer;
used,Oc:array[1..100,1..100] of integer;
och:array[1..1000000,1..4] of integer;
hi,lo:integer;
Ans:array[1..2,1..10000] of integer;

procedure calc;
var Z,X,y,C:integer;
begin
while lo<hi do
 begin
  inc(lo);
  X:=och[lo,1];Y:=och[lo,2];
  {try first}
  for i:=1 to A[X][0] do
   if A[X][i]<>Y then
    if (Vis[A[X][i],Y]=1) then
     begin
      Z:=A[X][i];
      if (Used[Z,Y]=-1) or (Used[Z,Y]>Used[X,Y]+1) then
        begin
         inc(hi);
         och[hi][1]:=Z;
         och[hi][2]:=Y;
         och[hi][3]:=lo;
         Used[Z,y]:=used[X,y]+1;
         oc[Z,y]:=hi;
         och[hi,4]:=och[lo,4]+1;
        end;
     end;
  {try Second}
  for i:=1 to A[Y][0] do
   if A[Y][i]<>X then
    if (Vis[A[Y][i],X]=1) then
     begin
      Z:=A[Y][i];
      if (Used[X,Z]=-1) or (Used[X,Z]>Used[X,Y]+1) then
        begin
         inc(hi);
         och[hi][1]:=X;
         och[hi][2]:=Z;
         och[hi][3]:=lo;
         Used[X,Z]:=used[X,y]+1;
         och[hi,4]:=och[lo,4]+1;
         oc[X,z]:=hi;
        end;
     end;
 {try Dual}
  for i:=1 to A[X][0] do
    for j:=1 to A[Y][0] do
      if (A[X][i]<>A[Y][j]) and ((A[X][i]<>Y) or (X<>A[Y][i])) then
       if (Vis[A[X][i],A[Y][j]]=1) then
         begin
          Z:=A[X][i];C:=A[Y][j];
           if (Used[Z,C]=-1) or (Used[Z,C]>Used[X,Y]+2) then
            begin
              inc(hi);
              och[hi][1]:=Z;
              och[hi][2]:=C;
              och[hi][3]:=lo;
              Used[Z,C]:=used[X,y]+2;
              oc[Z,c]:=hi;
              och[hi,4]:=och[lo,4]+1;
            end;
     end;

 end;
end;

procedure outData;
begin
 X:=oc[fx,fy];
 writeln(Used[fx,fy],' ',och[X,4]+1);i:=Och[X,4]+1;
 while X<>0 do
  begin
    Ans[1,i]:=Och[X,1];
    Ans[2,i]:=Och[X,2];
    X:=Och[X,3];
    dec(i);
  end;
 for i:=1 to Och[oc[fx,fy],4]+1 do
  writeln(Ans[1,i],' ',Ans[2,i]);
end;

begin
ASSIGN(input,'kingdom.in');reset(input);
assign(output,'kingdom.out');rewrite(output);
readln(N,M,Sx,Sy,Fx,Fy);
fillchar(A,sizeof(A),0);
fillchar(Vis,sizeof(Vis),0);
for i:=1 to N do
 for j:=1 to N do
  used[i,j]:=-1;
used[sx,sy]:=0;

for i:=1 to M do
 begin
   readln(X,Y);
   Vis[X,y]:=1;Vis[Y,X]:=1;
   inc(A[X][0]);A[X][A[X][0]]:=Y;
   inc(A[Y][0]);A[Y][A[Y][0]]:=X;
 end;
hi:=1;
lo:=0;
och[1,1]:=sx;
och[1,2]:=sy;
Och[1,3]:=0;Och[1,4]:=0;
calc;
outData;
close(output);
close(input);
end.
