{$APPTYPE CONSOLE}

uses SysUtils;
const maxn=1000000;
      maxQ = 2000 * 4;

var g1,g2:array[1..2100] of integer;
    f:array[1..100,1..100] of boolean;
    n,m,a1,a2,b1,b2,i,j,x,y,gn,n1,n2:integer;
    g:array[1..2000,1..2000] of integer;
    r:array[1..2000+239] of integer;

    was,obr:array[1..2004] of boolean;
    p:array[1..2004] of integer;
    pc:integer;

procedure EvaluateR;
var i,j,min:integer;
begin
 fillchar(was,sizeof(was),0);
 fillchar(obr,sizeof(obr),0);
 for i:=1 to gn do
  R[i]:=maxn;
 R[n1]:=0;
 was[n1]:=true;
 repeat
  min:=maxn;
  j:=-1;
  for i:=1 to gn do
   if (was[i]) and (R[i]<min) then begin j:=i; min:=R[i]; end;
  if j=-1 then break;
  was[j]:=false;
  obr[j]:=true;
  for i:=1 to gn do
   if (G[j,i]<maxn) and not obr[i] then
    begin
     was[i]:=true;
     if R[i]>R[j]+G[j,i] then R[i]:=R[j]+G[j,i];
    end;    
 until false;

// writeln(R[n2]);
end;

procedure EvaluatePath;
var i{,curP},curV:integer;
begin
 Pc:=1;
 P[1]:=n2;
// CurP:=R[n2];
 curV:=n2;
 while curV<>n1 do
  begin
   for i:=1 to gn do
    if (i<>curV) and (G[i,curV]+R[i]=R[curV]) then
     begin
      inc(Pc);
      p[pc]:=i;
      curV:=i;
      //curP:=curP-G[i,curV];
      break;
     end;
  end;
end;

begin
  reset(input,'kingdom.in');
  rewrite(output,'kingdom.out');
  fillchar(f,sizeof(f),0);
  read(n,m,a1,b1,a2,b2);
  for i:=1 to n do
   f[i,i]:=true;
  gn:=0;
  for i:=1 to m do
   begin
     read(x,y);
     if (x<>y) and not f[x,y] then
      begin
        inc(gn);
        g1[gn]:=x;
        g2[gn]:=y;
        if (a1=x) and (b1=y) then
         n1:=gn;
        if (a2=x) and (b2=y) then
         n2:=gn;
        inc(gn);
        g1[gn]:=y;
        g2[gn]:=x;
        if (a1=y) and (b1=x) then
         n1:=gn;
        if (a2=y) and (b2=x) then
         n2:=gn;
      end;
     f[x,y]:=true;
     f[y,x]:=true;
   end;
  for i:=1 to gn do
   for j:=1 to gn do
    g[i,j]:=maxn;
  for i:=1 to gn do
   for j:=1 to gn do
    begin
      if (g1[i]=g1[j]) and (g2[i]<>g2[j]) and f[g2[i],g2[j]] then
       begin
         g[i,j]:=1;
         continue;
       end;
      if (g1[i]<>g1[j]) and (g2[i]=g2[j]) and f[g1[i],g1[j]] then
       begin
         g[i,j]:=1;
         continue;
       end;
      if (g1[i]<>g1[j]) and (g2[i]<>g2[j]) and f[g1[i],g1[j]] and f[g2[i],g2[j]] and (g[i,j]>2) and
         not ((g1[i]=g2[i]) and (g1[j]=g2[j])) and not ((g1[i]=g2[j]) and (g1[j]=g2[i])) 
       then
       begin

         g[i,j]:=2;
         continue;
       end;
    end;

 for i:=1 to gn do G[i,i]:=0;

{ gn:=3;
 g[1,1]:=0; g[1,2]:=1; g[1,3]:=123;
 g[2,1]:=1; g[2,2]:=0; g[2,3]:=1;
 g[3,1]:=1; g[3,2]:=1; g[3,3]:=0;
 n1:=1;
 n2:=3;}

 EvaluateR;

 EvaluatePath;

 writeln(r[n2],' ',Pc);
 for i:=pc downto 1 do
  writeln(g1[p[i]],' ',g2[p[i]]);
end.
