{$apptype console}
{ $q+,r+,o-}
{$q+,r+,o+}
{ $q-,r-,o+}

uses
  math, sysutils;

const
  maxq = 500000;
  maxr = 500000;

type
  int = longint;
  bool = boolean;
  float = extended;
  tedge = record
    u, v: integer;
  end;

  tqueue = object
    dx, dy: array[1..maxq] of integer;
    size, head, tail: integer;

    procedure init;
    procedure add( x, y: integer );
    procedure get( var x, y: integer );
  end;

procedure tqueue.init;
begin
  size := 0;
  head := 1;
  tail := 1;
end;

procedure tqueue.add( x, y: integer );
begin
  inc( size );
  dx[tail] := x;
  dy[tail] := y;
  inc( tail );
  if ( tail > maxq ) then tail := 1;
end;

procedure tqueue.get( var x, y: integer );
begin
  dec( size );
  x := dx[head];
  y := dy[head];
  inc( head );
  if ( head > maxq ) then head := 1;
end;

const
  fn = 'kingdom';
  maxn = 105;
  maxm = 1005;

var
  n, m, a1, b1, a2, b2: integer;
  g: array[1..maxn, 1..maxn] of boolean;
  ind: array[1..maxn, 1..maxn] of integer;
  e: array[1..maxm] of tedge;

  res: array[1..maxr] of tedge;
  rc: integer;

  preva, prevb, d: array[1..maxn, 1..maxn] of integer;
  q: tqueue;
  inf: integer;

procedure swapmin( var x, y: integer );
var
  t: integer;
begin
  if ( x > y ) then begin
    t := x; x := y; y := t;
  end;
end;

procedure readdata;
var
  i: integer;
begin
  fillchar( g, sizeof( g ), false );
  fillchar( ind, sizeof( ind ), 0 );

  read( n, m, a1, b1, a2, b2 );
  
  for i := 1 to m do begin
    read( e[i].u, e[i].v );
    swapmin( e[i].u, e[i].v );
    
    g[e[i].u, e[i].v] := true;
    g[e[i].v, e[i].u] := true;
    ind[e[i].u, e[i].v] := i;
    ind[e[i].v, e[i].u] := i;
  end;
end;

procedure solve;
var
  ta, tb, k, ca, cb, i: integer;
begin
  fillchar( preva, sizeof( preva ), 0 );
  fillchar( prevb, sizeof( prevb ), 0 );
  fillchar( d, sizeof( d ), 63 );
  inf := d[1, 1];

  d[a1, b1] := 0;
  q.init;
  q.add( a1, b1 );
  while ( q.size > 0 ) do begin
    q.get( ca, cb );
    for i := 1 to m do
    if not ( (( e[i].u = ca ) and ( e[i].v = cb )) or (( e[i].v = ca ) and ( e[i].u = cb )) )  then begin
      if ( g[ca, e[i].u] ) and ( g[cb, e[i].v] ) then begin
        if ( d[e[i].u, e[i].v] > d[ca, cb] + 2 ) then begin
          d[e[i].u, e[i].v] := d[ca, cb] + 2;
          preva[e[i].u, e[i].v] := ca;
          prevb[e[i].u, e[i].v] := cb;
          q.add( e[i].u, e[i].v );
        end;
      end;

      if ( g[ca, e[i].v] ) and ( g[cb, e[i].u] ) then begin
        if ( d[e[i].v, e[i].u] > d[ca, cb] + 2 ) then begin
          d[e[i].v, e[i].u] := d[ca, cb] + 2;
          preva[e[i].v, e[i].u] := ca;
          prevb[e[i].v, e[i].u] := cb;
          q.add( e[i].v, e[i].u );
        end;
      end;
    end;

    for i := 1 to n do begin
      if ( g[ca, i] ) and ( g[i, cb] ) then begin
        if ( d[i, cb] > d[ca, cb] + 1 ) then begin
          d[i, cb] := d[ca, cb] + 1;
          preva[i, cb] := ca;
          prevb[i, cb] := cb;
          q.add( i, cb );
        end;
      end;

      if ( g[cb, i] ) and ( g[i, ca] ) then begin
        if ( d[ca, i] > d[ca, cb] + 1 ) then begin
          d[ca, i] := d[ca, cb] + 1;
          preva[ca, i] := ca;
          prevb[ca, i] := cb;
          q.add( ca, i );
        end;
      end;
    end;
  end;

  ca := a2;
  cb := b2;
  rc := 0;
  while true do begin
    if ( ca = a1 ) and ( cb = b1 ) then break;
    inc( rc );
    res[rc].u := ca;
    res[rc].v := cb;

    ta := preva[ca, cb];
    tb := prevb[ca, cb];
    ca := ta;
    cb := tb;
  end;
  inc( rc );
  res[rc].u := a1;
  res[rc].v := b1;

  writeln( d[a2, b2], ' ', rc );
  for i := rc downto 1 do
    writeln( res[i].u, ' ', res[i].v );
end;

begin
  reset(input, fn + '.in');
  rewrite(output, fn + '.out');

  readdata;
  solve;
end.
