{$O+,R-,Q-}
const
  inf = 1000000;
var
 res, j, i,n, m:longint;
 g:array[1..100, 1..100] of longint;
 a1, b1, a2, b2: integer;
 was, p, l, e1, e2: array[1..2000] of integer;
 a, b, es: integer;
 cur, s, e: integer;


function can1( a1, b1, a2, b2: integer ): boolean;
  begin
    if ( a1 = a2 ) and ( g[b1][b2]  = 1 ) then can1 := true
    else if ( b1 = b2 ) and ( g[a1][a2] = 1 ) then can1 := true
    else can1 := false;
  end;

function can2( a1, b1, a2, b2: integer ): boolean;
  begin
    can2 := ((  a1 <> b2 ) or ( b1 <> a2 ) ) and ( g[a1][a2] = 1 )and ( g[b1][b2] = 1 ); 
  end;


begin
 assign(input,'kingdom.in'); reset(input);
 assign(output,'kingdom.out'); rewrite(output);
 read(n, m, a1, b1, a2, b2);
 es := 0;
 for i := 1 to m do begin
   read( a, b );
   if a = b then continue;
   if g[a][b] = 1 then continue;
   inc( es );
   e1[es] := a;
   e2[es] := b;
   inc( es );
   e2[es] := a;
   e1[es] := b;
   g[a][b] := 1;
   g[b][a] := 1;
 end;
 for i := 1 to es do
   l[i] := inf;
 s := 0; e := 0;
 for i := 1 to es do begin
   if ( e1[i] = a1 ) and ( e2[i] = b1 ) then s := i;
   if ( e1[i] = a2 ) and ( e2[i] = b2 ) then e := i;
 end;
 l[e] := 0;
 cur := e;
 p[e] := -1;
 while true do begin
   for i := 1 to es do begin
     if ( l[i] > l[cur] + 1 ) and ( can1( e1[cur], e2[cur], e1[i], e2[i] ) ) then begin
       l[i] := l[cur] + 1;
       p[i] := cur;
     end;
     if ( l[i] > l[cur] + 2 ) and ( can2( e1[cur], e2[cur], e1[i], e2[i] ) ) then begin
       l[i] := l[cur] + 2;
       p[i] := cur;
     end;
   end;
   was[cur] := 1;

   cur := -1;
   for j := 1 to es  do begin
     if was[j] = 1 then continue;
     if l[j] = inf then continue;
     if ( cur = -1 ) or ( l[cur] > l[j] ) then
       cur := j;
   end;

   if cur = -1 then break;
   if cur = s then break;
 end;
 res := 0;
 i := s;
 while ( p[i] <> -1 ) do begin
   i := p[i];
   inc( res );
 end;
 writeln( l[s], ' ', res + 1 );
 i := s;
 while ( p[i] <> -1 ) do begin
   writeln( e1[i], ' ', e2[i] );
   i := p[i];
 end;
 writeln( e1[i], ' ', e2[i] );

end.
