{.$define debug}

{$apptype console}

{$ifdef debug}
{$R+,S+,Q+,I+,O-}
{$else}
{$R+,S-,Q+,I-,O+}
{$endif}

{$assertions on}
{$apptype console}

program template;
uses
 SysUtils;
const
 nmax = 110;
 mmax = 2100;
 inf = 10000000;
 {$ifdef debug}
 cinfile = 'input.txt';
 coutfile = 'output.txt';
 {$else}
 cinfile = 'kingdom.in';
 coutfile = 'kingdom.out';
 {$endif}
type
 int = longint;
 real = extended;
 tRib = record
  a,b :int;
 end; 
var
 n :int;
 m :int;
 ribs :array [1..mmax] of tRib;
 gr :array [1..nmax,1..nmax] of boolean;
 d :array [1..mmax] of int;
 used :array [1..mmax] of boolean;
 prev :array [1..mmax] of int;
 path :array [1..mmax] of int;
 vCount :int;
 start,finish :tRib;
 vst,vfn :int;
 ans :int;

procedure init;
begin
 fillchar (n,integer(@ans) - integer(@n),0);
 ans := 0;
end;

procedure swap (var a,b :int);
begin
 a := a xor b;
 b := a xor b;
 a := a xor b;
end;

procedure modify (var rib :tRib);
begin
 if rib.a > rib.b then
  swap (rib.a,rib.b);
end;

function q (const a,b :trib):boolean;
begin
 result := (a.a = b.a) and (a.b = b.b);
end;

procedure readdata;
var i,j :int;
begin
 assign (input,cinfile);
 reset (input);
 read (n,m);
 read (start.a,start.b,finish.a,finish.b);
 for i := 1 to m do
  begin
   read (ribs[2*i-1].a,ribs[2*i-1].b);
   ribs[2*i].a := ribs[2*i-1].b;
   ribs[2*i].b := ribs[2*i-1].a;
   
   gr[ribs[2*i].a,ribs[2*i].b] := true;
   gr[ribs[2*i-1].a,ribs[2*i-1].b] := true;
   
   if q (ribs[2*i],start) then
    vst := 2*i;
   if q (ribs[2*i],finish) then
    vfn := 2*i;

   if q (ribs[2*i - 1],start) then
    vst := 2*i - 1;
   if q (ribs[2*i - 1],finish) then
    vfn := 2*i - 1;
  end;
 m := 2*m;  
 close (input);
end;

procedure outdata;
var i,j :int;
begin
 assign (output,coutfile);
 rewrite (output);
 writeln (ans,' ',vCount);
 for i := vCount downto 1 do
  writeln (ribs[path[i]].a,' ',ribs[path[i]].b);
 close (output);
end;

function weight (const r1,r2 :tRib):int;
begin
 result := 0;
 if q(r1,r2) then
  exit;
 result := inf;
 if (r1.a = r2.b) and (r1.b = r2.a) then
  exit;
 if (r1.a = r2.a) then
  begin
   if gr[r1.b,r2.b] then
    result := 1
   else
    result := inf;
   exit; 
  end;
 if (r1.b = r2.b) then
  begin
   if gr[r1.a,r2.a] then
    result := 1
   else
    result := inf;
   exit;
  end;
 if gr[r1.a,r2.a] and gr[r1.b,r2.b] then
  result := 2
 else
  result := inf;
end;

procedure solve;
var i,j :int;
    res :int;
    cur :int;
    t :int;
begin
 assert ((vst <> 0) and (vfn <> 0));
 for i := 1 to m do
  d[i] := inf;
 d[vst] := 0;
 for i := 1 to m do
  begin
   res := inf;
   cur := 0;
   for j := 1 to m do
    if not used[j] then
     if d[j] < res then
      begin
       res := d[j];
       cur := j;
      end;
   if (cur = 0) then
    break;
   used[cur] := true;
   for j := 1 to m do
    begin
     t := d[cur] + weight(ribs[cur],ribs[j]);
     if d[j] > t then
      begin
       d[j] := t;
       prev[j] := cur;
      end;
    end;
  end;
 cur := vfn;
 while cur <> 0 do
  begin
   inc (vCount);
   path[vCount] := cur;
   cur := prev[cur];
  end;
 ans := d[vfn];
 assert (ans < inf - 100);  
end;

begin
 init;
 readdata;
 solve;
 outdata;
end.
