program blank;

{$APPTYPE CONSOLE}
{$D-,L-,I-,S-,Q-,R-,P-}

uses
  SysUtils;
const
  taskid='kingdom';
  infile=taskid+'.in';
  outfile=taskid+'.out';
  maxn2=2000;
  maxn1=100;
  inf=maxlongint div 2;

var
  last,first,a1,a2,b1,b2,n,m,tail,head:longint;
  b:array[1..maxn1,1..maxn1] of longint;
  a:array[1..maxn2,1..maxn2] of longint;
  e:array[1..maxn2,1..2] of longint;
  flag:array[1..maxn2] of boolean;
  p,d,path:array[0..maxn2] of longint;

function check(u,v:longint):longint;
begin
  if abs(u-v) = m then
  begin
    check:=inf;
    exit;
  end;
  if (e[u,1]=e[v,1])or(e[u,2]=e[v,2]) then
  begin
    check:=1;
    exit;
  end;
  if ((b[e[u,1],e[v,1]]<>0)and(b[e[u,2],e[v,2]]<>0))or((b[e[u,1],e[v,2]]<>0)and(b[e[u,2],e[v,1]]<>0))
      or(e[u,1]=e[v,2])or(e[u,2]=e[v,1]) then
  begin
    check:=2;
    exit;
  end;
  check:=inf;
end;
{--------------------------------------------------------------------}
Procedure Lesen;
var
  i,u,v,j:longint;
Begin
  read(n,m,a1,b1,a2,b2);
  for i:=1 to m do
  begin
    read(u,v);
    b[u,v]:=i;
    b[v,u]:=i+m;
    e[i,1]:=u; e[i+m,1]:=v;
    e[i,2]:=v; e[i+m,2]:=u;
  end;
  first:=b[a1,b1];
  last:=b[a2,b2];
  for i:=1 to 2*m do
    for j:=1 to 2*m do
      a[i,j]:=check(i,j);
end;

{--------------------------------------------------------------------}
Procedure Run;
var
  i,j,k,mmin:longint;
Begin
  for i:=1 to 2*m do
  begin
    d[i]:=inf;
  end;
  d[first]:=0;
  fillchar(flag,sizeof(flag),false);
  fillchar(p,sizeof(p),0);
  for i:=1 to 2*m do
  begin
    k:=-1; mmin:=inf;
    for j:=1 to 2*m do
    begin
      if (d[j]<mmin)and(flag[j]=false) then
      begin
        k:=j;
        mmin:=d[j];
      end;
    end;
    if k=-1 then
      break;
    d[k]:=mmin;
    flag[k]:=true;
    for j:=1 to 2*m do
    begin
      if (flag[j]=false)and(a[k,j]<>inf)and(d[k]+a[k,j]<d[j]) then
      begin
        d[j]:=d[k]+a[k,j];
        p[j]:=k;
      end;
    end;
  end;
  k:=last;
  while k<>0 do
  begin
    inc(path[0]);
    path[path[0]]:=k;
    k:=p[k];
  end;
end;
{--------------------------------------------------------------------}
Procedure done;
var
  i:longint;
begin
  writeln(d[last],' ',path[0]);
  for i:=path[0] downto 1 do
    writeln(e[path[i],1],' ',e[path[i],2]);
end;
{--------------------------------------------------------------------}

begin
  assign(input,infile);  reset(input);
  assign(output,outfile);  rewrite(output);
  lesen;
  run;
  done;
  close(input);  close(output);
end.
