program taskK;

{$APPTYPE CONSOLE}

uses
  SysUtils;
var
  i,j,l1,l2,n,m,dotv:longint;
  k1,k2,n1,n2:longint;
  a:array[1..101,1..101]of byte;
  b:array[1..101,0..101]of byte;
  mem:array[1..101,1..101]of longint;
  otv,put:array[0..10001]of array[1..2]of longint;
  lenotv:longint;
Procedure rec(t1,t2,t3,t4:longint);
var
  ii,jj:longint;
begin
  if mem[t1][t2]<=t3 then exit;
  if a[t1][t2]=0 then exit;
  if t1=t2 then exit;
  put[t4][1]:=t1;
  put[t4][2]:=t2;
  mem[t1][t2]:=t3;
  if (t1=k1)and(t2=k2) then
  begin
    otv:=put;
    lenotv:=t4;
    dotv:=t3;
    exit;
  end;
  for ii:=1 to b[t1][0] do rec(b[t1][ii],t2,t3+1,t4+1);
  for ii:=1 to b[t2][0] do rec(t1,b[t2][ii],t3+1,t4+1);

  for ii:=1 to b[t1][0] do
    for jj:=1 to b[t2][0] do
      if (b[t1][ii]<>t2)or(b[t2][jj]<>t1) then
        rec(b[t1][ii],b[t2][jj],t3+2,t4+1);
end;
begin
assign(input,'kingdom.in');reset(input);
assign(output,'kingdom.out');rewrite(output);
readln(n,m,n1,n2,k1,k2);
for i:=1 to m do
begin
  read(l1,l2);
  a[l1][l2]:=1;
  a[l2][l1]:=1;
  inc(b[l1][0]);
  b[l1][b[l1][0]]:=l2;
  inc(b[l2][0]);
  b[l2][b[l2][0]]:=l1;
end;
fillchar(mem,sizeof(mem),127);
rec(n1,n2,0,0);
writeln(dotv,' ',lenotv+1);
for i:=0 to lenotv do writeln(otv[i][1],' ',otv[i][2]); 

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