{$APPTYPE CONSOLE}
{$Q-,R-}
const
  inf = maxlongint;
var
  n,m,a1,b1,a2,b2,i,j,k,u,v,s,t,x,y,min:longint;
  ne1:array[1..110]of longint;
  p1,p2:array[1..1100]of longint;
  num:array[1..110,1..110]of longint;
  e1:array[1..1100,1..1100]of longint;
  e,w:array[1..2100,1..2100]of longint;
  d,l,p,ne,was:array[1..2100]of longint;

begin
  assign(input,'kingdom.in'); reset(input);
  assign(output,'kingdom.out'); rewrite(output);
  read(n,m,a1,b1,a2,b2);
  for i:=1 to m do begin
    read(u,v);
    p1[i]:=u; p2[i]:=v; num[u,v]:=i; num[v,u]:=i+m;
    inc(ne1[u]);e1[u,ne1[u]]:=v;
    inc(ne1[v]);e1[v,ne1[v]]:=u;
    if (u=a1)and(v=b1)then s:=i;
    if (u=b1)and(v=a1)then s:=m+i;
    if (u=a2)and(v=b2)then t:=i;
    if (u=b2)and(v=a2)then t:=m+i;
  end;
  for i:=1 to m do begin
    u:=p1[i]; v:=p2[i];
    for j:=0 to ne1[u] do
    for k:=0 to ne1[v] do begin
      if j=0 then x:=u else x:=e1[u,j];
      if k=0 then y:=v else y:=e1[v,k];
      if (x=u)and(y=v) then continue;
      if (y=u)and(x=v) then continue;
      if x=y then continue;
      if num[x,y]=0 then continue;
      inc(ne[i]); e[i,ne[i]]:=num[x,y];
      inc(ne[i+m]);e[i+m,ne[i+m]]:=num[y,x];
      if (x<>u)and(y<>v)then begin
        w[i,num[x,y]]:=2;
        w[i+m,num[y,x]]:=2;
      end else begin
        w[i,num[x,y]]:=1;
        w[i+m,num[y,x]]:=1;
      end;
    end;
  end;
  for i:=1 to 2*m do d[i]:=inf;
  d[t]:=0; l[t]:=0;
  while was[s]=0 do begin
    min:=inf;
    for i:=1 to 2*m do if (was[i]=0)and(d[i]<min) then begin
      v:=i; min:=d[i];
    end;
    was[v]:=1;
    for i:=1 to ne[v] do if d[e[v,i]]>d[v]+w[v,e[v,i]] then begin
      d[e[v,i]]:=d[v]+w[v,e[v,i]];
      p[e[v,i]]:=v;
      l[e[v,i]]:=l[v]+1;
    end;
  end;
  writeln(d[s],' ',l[s]+1);
  u:=s;
  while u<>t do begin
    if u<=m then writeln(p1[u],' ',p2[u]) else
                 writeln(p2[u-m],' ',p1[u-m]);
    u:=p[u];
  end;
  if u<=m then writeln(p1[u],' ',p2[u]) else
               writeln(p2[u-m],' ',p1[u-m]);
end.
 