const
  InFile  = 'kingdom.in';
  OutFile = 'kingdom.out';

var
  inf, outf : textfile;
  n, m, CM1, CF1, CM2, CF2 : integer;
  Conns : array[1..1000, 1..2] of integer; 
  All : array[1..100, 1..100] of integer;
  step : integer;
  fl : boolean;
  st : integer;
  otv : array [1..1000, 1..2] of integer;
  jumps : integer;
  
procedure Init;
var i : integer;
begin
  Assign(inf, InFile);
  Assign(outf, OutFile);
  Reset(inf);
  Rewrite(outf);
  Read(inf, n, m, CM1, CF1, CM2, CF2);
  for i := 1 to m do 
  begin
    Read(inf, Conns[i, 1], Conns[i, 2]);
  end;
  all[CM1, CF1] := 1;
end;

function Exist(a, b: integer):boolean;
var i : integer;
begin
  for i := 1 to m do
  begin
    if ((Conns[i,1] = a) and (Conns[i,2] = b)) or  ((Conns[i,2] = a) and (Conns[i,1] = b)) then
    begin
      Exist := true;
      exit;
    end;
  end;
  Exist := false;
end;

procedure Fill (a, b : integer);
begin
        All[a, b] := step + 1;
        if (a = CM2) and (b = CF2) then
        begin
          fl := false;
        end;
end;


procedure Start2(a1, b1 : integer);
var i, j : integer;
begin
  for i := 1 to m do
  begin
    if (b1 = Conns[i, 1]) then
    begin
      if (Exist(a1, Conns[i, 2]) and (All[a1, Conns[i, 2]] = 0)) then
      begin
        Fill (a1, Conns[i,2]);
      end;
      if (not Exist(a1, Conns[i, 2])) then
      begin
        for j := 1 to m do
        begin
          if (j = b1) and (Conns[i, 2] = a1) then continue;
          if (Exist(j, Conns[i, 2]) and (All[j, Conns[i, 2]] = 0)  and Exist(a1, j)) then
          begin
            Fill(j, Conns[i, 2]);
          end;
        end;
      end;
    end;
    if (b1 = Conns[i, 2]) then
    begin
      if (Exist(a1, Conns[i, 1]) and (All[a1, Conns[i, 1]] = 0)) then
      begin
        Fill (a1, Conns[i,1]);
      end;
      if (not Exist(a1, Conns[i, 1])) then
      begin
        for j := 1 to m do
        begin
          if (j = b1) and (Conns[i, 1] = a1) then continue;
          if (Exist(j, Conns[i, 1]) and (All[j, Conns[i, 1]] = 0)  and Exist(a1, j)) then
          begin
            Fill(j, Conns[i, 1]);
          end;
        end;
      end;

    end;
  end;
end;


procedure Start1(a1, b1 : integer);
var i, j : integer;
begin
  for i := 1 to m do
  begin
    if (a1 = Conns[i, 1]) then
    begin
      if (Exist(Conns[i, 2], b1) and (All[Conns[i, 2], b1] = 0)) then
      begin
        Fill (Conns[i, 2], b1);
      end;
      if (not Exist(Conns[i, 2], b1)) then
      begin
        for j := 1 to m do
        begin
          if (j = a1) and (Conns[i, 2] = b1) then continue;
          if (Exist(Conns[i, 2], j) and (All[Conns[i, 2], j] = 0) and Exist(b1, j)) then
          begin
            Fill(Conns[i, 2], j);
          end;
        end;
      end;

    end;
    if (a1 = Conns[i, 2]) then
    begin
      if (Exist(Conns[i, 1], b1) and (All[Conns[i, 1], b1] = 0)) then
      begin
        Fill (Conns[i, 1], b1);
      end;
      if (not Exist(Conns[i, 1], b1)) then
      begin
        for j := 1 to m do
        begin
          if (j = a1) and (Conns[i, 1] = b1) then continue;
          if (Exist(Conns[i, 1], j) and (All[Conns[i, 1], j] = 0)  and Exist(b1, j)) then
          begin
            Fill(Conns[i, 1], j);
          end;
        end;
      end;
    end;

  end;
end;

procedure Run;
var 
  i,j,k,l : integer;
  fll : boolean;
begin
  fl := true;
  step := 1;
  while fl do
  begin
    for i := 1 to n do
    begin
      for j := 1 to n do
      begin                                         
        if (all[i,j] = step) then
        begin
          Start1(i, j);
          Start2(i, j);
        end;
      end;
    end;
    step := step +1;
  end;
  st := step;
  otv[step, 1] := CM2;
  otv[step, 2] := CF2;
  step := step - 1;
  jumps := 0;
  while step >= 1 do
  begin
    fll := false;
    for i := 1 to n do
    begin
      for j := 1 to n do
      begin
        if (all[i, j] = step) then
        begin
          if ( (j = CF2) and (Exist(i, CM2))) or ((i = CM2) and (Exist(j, CF2))) or (Exist(i,CM2) and Exist(j, CF2)) then
          begin
            if ( (j = CF2) and Exist(i, CM2) ) or ( (i = CM2) and Exist(j, CF2) ) then 
              jumps := jumps + 1
            else
              jumps := jumps + 2;
          otv[step, 1] := i;
          otv[step, 2] := j;
          CM2 := i;
          CF2 := j;
          step := step - 1;
          fll := true;
          break;
          end;
        end;
      end;
      if fll then break;
    end;
  end;
end;

procedure Done;
var i : integer;
begin
  writeln(outf, jumps,' ', st);
  for i := 1 to st do
  begin
    writeln(outf, otv[i, 1], ' ', otv[i, 2]);
  end;
  Close(inf);
  Close(outf);
end;


begin
  Init;
  Run;
  Done;
  Halt(0);
end.