program progk;

{$APPTYPE CONSOLE}

uses
  classes, sysutils;

type pmove=^tmove;
     tmove=record
             a,b: byte;
             next: pmove;
           end;

const
  maxm= 100;

var f: text;
    mv: array[1..maxm, 1..maxm] of word;
    iss: array[1..maxm, 1..maxm] of record a, b: byte; end;
    g: array [1..maxm, 0 .. maxm] of byte;
    gb: array[1..maxm, 1..maxm] of boolean;
    i,n,m,a1,b1,a2,b2,x,y: word;
    nagr, last: pmove;

const maxword = 65000;

function canmove (af,bf,at,bt: byte): boolean;
begin
  result := gb[at,bt] and not ((af = bt) and (bf = at)) and (at <> bt);
end;


procedure move (a,b: byte);
  var ai, bi: byte;
begin
  for ai := 1 to g[a,0] do
    if canmove(a, b, g[a, ai], b) and (mv[a, b] +1< mv[g[a,ai], b]) then
      begin
        mv[g[a,ai], b] := mv[a, b] +1;
        iss[g[a,ai], b].a := a; iss[g[a,ai], b].b := b;
        new(last^.next);
        last := last^.next;
        last^.a := g[a,ai]; last^.b := b; last^.next := nil;
      end;

  for bi := 1 to g[b,0] do
    if canmove(a, b, a, g[b, bi]) and (mv[a, b] +1< mv[a, g[b,bi]]) then
      begin
        mv[a, g[b,bi]] := mv[a, b] +1;
        iss[a, g[b,bi]].a := a; iss[a, g[b,bi]].b := b;
        new(last^.next);
        last := last^.next;
        last^.a := a; last^.b := g[b,bi]; last^.next := nil;
      end;
  for ai := 1 to g[a,0] do
    for bi := 1 to g[b,0] do
      if canmove(a, b, g[a, ai], g[b, bi]) and (mv[a, b] +2< mv[g[a, ai], g[b,bi]]) then
      begin
        mv[g[a, ai], g[b,bi]] := mv[a, b] +2;
        iss[g[a, ai], g[b,bi]].a := a; iss[g[a, ai], g[b,bi]].b := b;
        new(last^.next);
        last := last^.next;
        last^.a := g[a,ai]; last^.b := g[b,bi]; last^.next := nil;
      end;
end;

procedure solve;
var
  p: pmove;
begin
  while nagr <> nil do
  begin
    move(nagr^.a, nagr^.b);
    p := nagr;
    nagr := nagr^.next;
    dispose(p);
  end;
end;

var
  ats: TStringList;
  at, bt, att, btt: byte;

begin
  fillchar (mv, sizeof(mv), 255);
  fillchar (g, sizeof(g), 0);
  fillchar (gb, sizeof(gb), 0);
  assign (f, 'kingdom.in');
  reset (f);
  readln (f, n,m,a1,b1,a2,b2);
  if n =1 then;
  for i := 1 to m do
  begin
    readln (f, x,y);
    inc(g[x,0]); g[x,g[x,0]] := y;
    inc(g[y,0]); g[y,g[y,0]] := x;
    gb[x,y] := true;
    gb[y,x] := true;
  end;
  mv[a1,b1] := 0;
  new (nagr);
  nagr^.a := a1;
  nagr^.b := b1;
  nagr^.next := nil;
  last := nagr;
  close (f);

  solve;

  assign (f, 'kingdom.out');
  rewrite(f);
  ats := TStringList.create;
  at := a2; bt := b2;
  ats.Add(inttostr(at) + ' ' + inttostr(bt));
  while (at <> a1) or (bt <> b1) do
  begin
    att := at; btt := bt;
    at := iss[att, btt].a; bt := iss[att, btt].b;
    ats.Add(inttostr(at) + ' ' + inttostr(bt));
  end;
  writeln(f, mv[a2, b2], ' ', ats.Count);
  for i := ats.Count-1 downto 0 do
    writeln(f, ats.strings[i]);
  ats.Free;
  close(f);
end.
