program zk;

{$APPTYPE CONSOLE}

uses
  SysUtils;
type
  TPair =
    record
      prev,len,x,y,n1,n2: integer;
      next1,next2: packed array[1..2000] of integer;
    end;
const
  queue_last= 1 shl 20 - 1;
var
  matr: array [1..100,1..100] of boolean;
  npairs: integer;
  pairs: array[1..2000] of TPair;
  n,m,a1,b1,a2,b2: integer;
  i,j,k: integer;
  x,y: integer;
  z,zz,z1,z2: integer;
  qhead,qtail: integer;
  queue: array[0..queue_last] of integer;
  path: array[1..2000] of integer;
  np: integer;
begin
  assign(input,'kingdom.in');
  assign(output,'kingdom.out');
  reset(input);
  rewrite(output);
  fillchar(matr,sizeof(matr),0);
  npairs := 0;
  read(n,m,a1,b1,a2,b2);
  for i := 1 to m do
    begin
      read(x,y);
      matr[x,y] := true;
      inc(npairs);
      if (x=a1) and (y=b1) then z1 := npairs;
      if (x=a2) and (y=b2) then z2 := npairs;
      pairs[npairs].x := x;
      pairs[npairs].y := y;
      matr[y,x] := true;
      inc(npairs);
      if (y=a1) and (x=b1) then z1 := npairs;
      if (y=a2) and (x=b2) then z2 := npairs;
      pairs[npairs].x := y;
      pairs[npairs].y := x;
    end;

  for i := 1 to npairs do
    begin
      pairs[i].n1 := 0;
      pairs[i].n2 := 0;
      pairs[i].len := high(integer);
      pairs[i].n2 := -1;
      for j := 1 to npairs do
        begin
          if (pairs[i].x=pairs[j].x)and matr[pairs[i].y][pairs[j].y] or
            (pairs[i].y=pairs[j].y)and matr[pairs[i].x][pairs[j].x] then
            begin
              inc(pairs[i].n1);
              pairs[i].next1[pairs[i].n1] := j;
            end;
          if matr[pairs[i].x][pairs[j].x] and matr[pairs[i].y][pairs[j].y] and
            not ((pairs[i].x=pairs[j].y)and(pairs[i].y=pairs[j].x)) then
            begin
              inc(pairs[i].n2);
              pairs[i].next2[pairs[i].n2] := j;
            end;
        end;
    end;
  qhead := 0;
  qtail := 1;
  queue[0] := z1;
  pairs[z1].len := 0;
  repeat
    z := queue[qhead];
    qhead := (qhead+1) and queue_last;
    for i := 1 to pairs[z].n1 do
      begin
        zz := pairs[z].next1[i];
        if pairs[z].len+1<pairs[zz].len then
          begin
            pairs[zz].len := pairs[z].len+1;
            pairs[zz].prev := z;
            queue[qtail] := zz;
            qtail := (qtail+1) and queue_last;
          end;
      end;
    for i := 1 to pairs[z].n2 do
      begin
        zz := pairs[z].next2[i];
        if pairs[z].len+2<pairs[zz].len then
          begin
            pairs[zz].len := pairs[z].len+2;
            pairs[zz].prev := z;
            queue[qtail] := zz;
            qtail := (qtail+1) and queue_last;
          end;
      end;
  until qtail=qhead;
  np := 1;
  path[1] := z2;
  while path[np]<>z1 do
    begin
      path[np+1] := pairs[path[np]].prev;
      inc(np);
    end;
  writeln(pairs[z2].len,' ',np);
  for i := np downto 1 do
    writeln(pairs[path[i]].x,' ',pairs[path[i]].y);
{for i := 1 to npairs do writeln('q ',pairs[i].x,' ',pairs[i].y, ' ' , pairs[i].prev);
writeln('z ', z1, ' ', z2);}
end.
