program kingdom;
const
 maxn=2002;
 maxk=102;
type
 tmap=array[1..maxn,1..maxn] of longint;
 tmas=array[1..maxn,1..2] of longint;
 tmas1=array[1..maxk,1..maxk] of boolean;
var
 z,u,v,i,j,ll,l,min,x,y,n,m,k,a1,a2,b1,b2:longint;
 r,t,d:array[1..maxn] of longint;
 a:tmap;
 c:tmas;
 p:tmas1;
 pt:array[1..maxn] of boolean;
begin
  assign(input,'kingdom.in');
  reset(input);
  assign(output,'kingdom.out');
  rewrite(output);

  readln(n,m,a1,b1,a2,b2);
  fillchar(p,sizeof(p),false);
  k:=0;
  for i:=1 to m do
  begin
    readln(u,v);
    p[u,v]:=true;
    p[v,u]:=true;
    inc(k);
    c[k,1]:=u;
    c[k,2]:=v;
    if (u=a1) and (v=b1) then x:=k;
    if (u=a2) and (v=b2) then y:=k;
    inc(k);
    c[k,1]:=v;
    c[k,2]:=u;
    if (v=a1) and (u=b1) then x:=k;
    if (v=a2) and (u=b2) then y:=k;
  end;

  for i:=1 to k do
  begin
    for j:=1 to k do if i<>j then
    begin
      a[i,j]:=1000000;
      if (c[i,1]=c[j,1]) and p[c[i,2],c[j,2]] then a[i,j]:=1 else
      if (c[i,2]=c[j,2]) and p[c[i,1],c[j,1]] then a[i,j]:=1 else
      if p[c[i,1],c[j,1]] and p[c[i,2],c[j,2]] then a[i,j]:=2;
      if (c[i,1]=c[j,2]) and (c[i,2]=c[j,1]) then a[i,j]:=1000000;
    end;
  end;

  for i:=1 to k do r[i]:=maxlongint;

  r[x]:=0;
  l:=x;
  fillchar(t,sizeof(t),0);
  fillchar(pt,sizeof(pt),true);
  pt[x]:=false;  
  for i:=1 to k do
  begin
    min:=maxlongint;
    for j:=1 to k do if a[l,j]<1000000 then
    begin
      if r[l]+a[l,j]<r[j] then
      begin
        r[j]:=a[l,j]+r[l];
        t[j]:=l;
      end;
      if (r[j]<min) and pt[j] then
      begin
        min:=r[j];
        ll:=j;
      end;
    end;
    l:=ll;
    pt[l]:=false;
  end;

  i:=y;
  z:=0;
  while i<>0 do
  begin
    inc(z);
    d[z]:=i;
    i:=t[i];
  end;

  writeln(r[y],' ',z);
  for i:=z downto 1 do
  begin
    writeln(c[d[i],1],' ',c[d[i],2]);
  end;  
  close(input);
  close(output);
end.
