{DEFINE DMI}
{DEFINE DO0}
{DEFINE DEBUG}
{$IFDEF DEBUG}
{$B-,I+,N+,O-,Q+,R+,S+}
{$ELSE}
{$B-,I-,N+,O+,Q-,R-,S-}
{$ENDIF}
{$APPTYPE CONSOLE}
Program OlympSol;
uses SysUtils;
const TaskName = 'kingdom';
 MaxN = 102; MaxM = 1003; MaxP = MaxM * 2; MaxC = 10000;
var i, j, k, l, m, n: Integer;
 adj0: array [1..MaxN, 1..MaxN] of Integer;
 adj: array [1..MaxP, 1..MaxP] of Integer;
 a, b: array [1..MaxP] of Integer;
 e: array [1..MaxP] of Boolean;
 w, par, moves: array [1..MaxP] of Integer;
 start, finish, cur, min, a1, b1, a2, b2, p: Integer;

BEGIN
 assign (input, TaskName + '.in'); reset (input);
 assign (output, TaskName + '.out'); rewrite (output);
{$IFDEF DMI} repeat {$ENDIF}
 read (n, m, a1, b1, a2, b2);
 fillchar (adj0, sizeof (adj0), 31);
 for i := 1 to m do begin
  read (a[i], b[i]);
  adj0[a[i]][b[i]] := 1;
  adj0[b[i]][a[i]] := 1;
 end;
 for i := 1 to m do begin
  b[i + m] := a[i];
  a[i + m] := b[i];
 end;
 for i := 1 to n do
  adj0[a[i]][a[i]] := 0;
 p := m * 2;
 fillchar (adj, sizeof (adj), 63);
 for i := 1 to p do
  for j := 1 to p do if abs (i - j) <> m then
   if (a[i] <> b[i]) OR (a[j] <> b[j]) then
    adj[i][j] := adj0[a[i]][a[j]] + adj0[b[i]][b[j]];

 start := 0;
 for i := 1 to p do
  if (a[i] = a1) AND (b[i] = b1) then begin
   start := i; break;
  end;
{$IFDEF DEBUG} assert (start <> 0); {$ENDIF}
 finish := 0;
 for i := 1 to p do
  if (a[i] = a2) AND (b[i] = b2) then begin
   finish := i; break;
  end;
{$IFDEF DEBUG} assert (finish <> 0); {$ENDIF}

 fillchar (w, sizeof (w), 30);
 fillchar (e, sizeof (e), 0);
 fillchar (moves, sizeof (moves), 0);
 fillchar (par, sizeof (par), 0);
 cur := finish;
 w[cur] := 0;
 repeat
{$IFDEF DO0} writeln (cur, ': ', a[cur], ' ', b[cur]); {$ENDIF}
  e[cur] := True;
  for i := 1 to p do if NOT e[i] then
   if w[i] > w[cur] + adj[cur][i] then begin
    w[i] := w[cur] + adj[cur][i];
    par[i] := cur;
    moves[i] := moves[cur] + 1;
   end;
  min := MaxC; k := 0;
  for i := 1 to p do if NOT e[i] then
   if min > w[i] then begin
    min := w[i];
    k := i;
   end;
  if k = 0 then break;
  cur := k;
 until False;
{$IFDEF DEBUG} assert (e[start]); {$ENDIF}

 writeln (w[start], ' ', moves[start] + 1);
 repeat
  writeln (a[start], ' ', b[start]);
  if start = finish then break;
  start := par[start];
 until False;
{$IFDEF DMI} until seekeof; {$ENDIF}
END.
