{$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}
const
	maxN = 105;
  maxM = 2010;
  cInf = 1000000000;

var
	n, m:		Integer;
  t:			array[1..maxN, 1..maxN] of Boolean;
  x:			array[1..maxM, 1..maxM] of Integer;
  d:			array[1..maxM] of Integer;
  prev:		array[1..maxM] of Integer;
  v:			array[1..maxM] of record a,b:Integer; end;
  a1,a2,b1,b2: Integer;
  s,f: Integer;
  nm:			Integer;

function pair(i,j: Integer): Boolean;
begin
	pair := (v[i].a<>v[j].b)and(v[i].a<>v[j].a)and(v[i].b<>v[j].b)and(v[i].b<>v[j].a)
end;

function tri(i,j: Integer): Boolean;
begin
	tri := not((v[i].a=v[j].b)and(v[i].b=v[j].a))
end;

Procedure Init;

procedure AddV(a,b: Integer);
begin
	inc(nm);
  v[nm].a := a; v[nm].b := b;
  if (a=a1)and(b=b1) then s := nm;
  if (a=a2)and(b=b2) then f := nm;
end;

var
	i,j : Integer;
  a,b,q: Integer;
  flag:	Boolean;
Begin
	read(n, m);
  read(a1, b1, a2, b2);
  fillchar(t, sizeof(t), 0);
  nm := 0;
  for i := 1 to m*2 do
  	for j := 1 to m*2 do x[i,j] := cInf;

  for i := 1 to m do begin
  	read(a, b);
    t[a,b] := True; t[b,a] := True;
    AddV(a,b); AddV(b,a);
  end;

  for i := 1 to nm do
  	for j := i+1 to nm do if i<>j then begin
    	flag := False;
    	if pair(i,j) then begin
      	flag := (t[v[i].a,v[j].a])and(t[v[i].b,v[j].b])//(t[v[i].a,v[j].a]and t[v[i].b,v[j].b])or(t[v[i].a,v[j].b]and t[v[i].a,v[j].b]);
      end
      else if tri(i,j) then begin
      	if v[i].a=v[j].a then begin
        	flag := t[v[i].b,v[j].b]
        end
        else if v[i].b=v[j].b then begin
        	flag := t[v[i].a,v[j].a]
        end{
      	else if v[i].a=v[j].b then begin
        	flag := t[v[i].b,v[j].a]
        end
      	else begin
        	flag := t[v[i].a,v[j].b]
        end}
      end;
      if flag then
      	if pair(i,j) then
        	x[i,j] := 2
        else x[i,j] := 1;
      x[j,i] := x[i,j];
    end;
End;

Procedure Solve;
var
	fl:	array[1..maxM] of Boolean;
  i,j:	Integer;
  p:		Integer;
  v:		Integer;
  finish:Boolean;
Begin
	fillchar(fl, sizeof(fl), False);
  for i := 1 to nm do begin
  	d[i] := cInf;
    prev[i] := 0;
  end;
  d[s] := 0;

  repeat
  	finish := true;
  	p := -1; v := cInf;
    for i := 1 to nm do
    	if (not fl[i])and(d[i]<v) then begin
      	finish := False;
        p := i;
        v := d[i];
      end;

    if not finish then begin
    	fl[p] := True;
    	for i := 1 to nm do if i<>p then
      	if v+x[p,i]<d[i] then begin
        	d[i] := v + x[p,i];
          prev[i] := p;
        end
    end;
  until finish;
End;

Procedure Save;
var
	now, num:	Integer;
  st:				array[1..maxM] of Integer;
  i: Integer;
Begin
	write(d[f], ' ');
  now := f; num := 0;
  while now<>s do begin
  	inc(num); st[num] := now;
    now := prev[now];
  end;
  inc(num); st[num] := s;
  writeln(num);

  for i := num downto 1 do
  	writeln(v[st[i]].a, ' ', v[st[i]].b);
End;

begin
assign(input,'kingdom.in'); reset(input);
assign(output,'kingdom.out'); rewrite(output);
  Init;
  Solve;
  Save;
close(input);
close(output);
end.
 