{$DEFINE DEBUG}

{$IFDEF DEBUG}
{$A+,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O-,P+,Q+,R+,S+,T-,U-,V+,W-,X+,Y+,Z1}
{$ELSE}
{$A+,B-,C+,D-,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q-,R-,S-,T-,U-,V+,W-,X+,Y+,Z1}
{$ENDIF}

{$MINSTACKSIZE $00004000}
{$MAXSTACKSIZE $02000000}
{$APPTYPE CONSOLE}

uses
  Math, SysUtils;

type
  int = longint;
  float = extended;

const
  maxn = 110;
  maxm = 210;
  maxv = 20000;
  maxd = 70000;
  cin_file = 'kingdom.in';
  cout_file = 'kingdom.out';
  eps : float = 1e-9;
  fmax : float = 1e40;
  besk = $3F3F3F3F;

var
  tsize,off,n,m,a1,b1,a2,b2 : int;
  a : array[1..maxn,1..maxn] of int;
  e : array[1..maxn,0..maxm] of int;
  ax,ay,from,d,md : array[1..maxd] of int;

procedure addEdge(i,j : int);
begin
  a[i,j]:=1;
  inc(e[i,0]);
  e[i,e[i,0]]:=j;
end;

function encode(i,j : int) : int;
begin
  encode:=i shl 7 + j;
end;

procedure decode(d : int; var i,j : int);
begin
  j:=d and 127;
  i:=d shr 7;
end;

procedure updone(k : int);
begin
  md[k]:=md[k shl 1];
  if (md[k] = 0) then md[k]:=md[k shl 1 + 1]
  else if (md[k shl 1 + 1] > 0) and (d[md[k]] > d[md[k shl 1 + 1]]) then md[k]:=md[k shl 1 + 1];
end;

procedure update(k : int);
begin
  k:=k shr 1;
  while k > 0 do
  begin
    updone(k);
    k:=k shr 1;
  end;
end;

procedure build(k : int);
begin
  if k > off then
  begin
    md[k]:=k - off;
  end else
  begin
    build(k shl 1);
    build(k shl 1 + 1);
    updone(k);
  end;
end;

procedure solve;
var
  cnt,p,q,t,src,dst,i,j,k,l : int;
begin
  read(n,m,a1,b1,a2,b2);
  fillchar(a, sizeof(a), 0);
  fillchar(e, sizeof(e), 0);
  for k:=1 to m do
  begin
    read(i,j);
    addEdge(i,j);
    addEdge(j,i);
  end;

  fillchar(d, sizeof(d), $3F);
  fillchar(md, sizeof(md), 0);
  fillchar(from, sizeof(from), 0);
  src:=encode(a1,b1);
  dst:=encode(a2,b2);

  d[src]:=0;

  t:=encode(n,n);
  tsize:=1;
  while tsize < t do tsize:=tsize shl 1;
  off:=tsize - 1;

  build(1);

  while from[dst] = 0 do
  begin
    l:=md[1];
    md[l + off]:=0;
    update(l + off);

    decode(l, i, j);

    for p:=1 to e[i,0] do
      for q:=1 to e[j,0] do
        if (a[ e[i,p], e[j,q] ] > 0) and ((e[i,p] <> j) or (e[j,q] <> i)) then
        begin
          t:=encode(e[i,p], e[j,q]);
          if d[t] > d[l] + 2 then
          begin
            d[t]:=d[l] + 2;
            from[t]:=l;
            update(t + off);
          end;
        end;

    for p:=1 to e[i,0] do
      if (a[e[i,p], j] > 0) then
      begin
        t:=encode(e[i,p], j);
        if d[t] > d[l] + 1 then
        begin
          d[t]:=d[l] + 1;
          from[t]:=l;
          update(t + off);
        end;
      end;

    for q:=1 to e[j,0] do
      if (a[i, e[j,q]] > 0) then
      begin
        t:=encode(i, e[j,q]);
        if d[t] > d[l] + 1 then
        begin
          d[t]:=d[l] + 1;
          from[t]:=l;
          update(t + off);
        end;
      end;
  end;


  i:=dst;
  cnt:=0;
  while i > 0 do
  begin
    j:=from[i];
    inc(cnt);
    decode(i, ax[cnt], ay[cnt]);
    i:=j;
  end;

  writeln(d[dst], ' ', cnt);
  for i:=cnt downto 1 do
    writeln(ax[i], ' ',ay[i]);
end;

begin
  assign(input, cin_file);
  reset(input);
  assign(output,  cout_file);
  rewrite(output);

  solve;

  close(input);
  close(output);
end.