{$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}
{$MAXSTACKSIZE $3C00000}
{$APPTYPE CONSOLE}
type
 int = integer;
 real = extended;
var
a,used: array[0..1001,0..1001] of boolean;
b: array[0..1001,0..1001] of integer;
pr: array[0..1001,0..1001,1..2] of integer;
queue,queue2: array[0..1000000,1..2] of integer;
r: array[0..1000001] of integer;
n,m,s1,s2,f1,f2: integer;

procedure rec(x,y,s,k: integer);
begin
if (x=0) and (y=0) then
  begin
    writeln(k-2,' ',s);
    Exit;
  end;
if (x<>pr[x,y,1]) and (y<>pr[x,y,2]) then rec(pr[x,y,1],pr[x,y,2],s+1,k+2)
  else rec(pr[x,y,1],pr[x,y,2],s+1,k+1);
writeln(x,' ',y);
end;

function dif(e,f,i,j: integer): boolean;
begin
dif := ((e<>i)or(f<>j)) and ((e<>j)or(f<>i));
end;

var
i,j,e,f,h,t,d: integer;
begin
assign(input,'kingdom.in');reset(input);
assign(output,'kingdom.out');rewrite(output);
read(n,m,s1,s2,f1,f2);
for i:=1 to m do
  begin
    read(e,f);
    a[e,f]:=true;
    a[f,e]:=true;
    inc(b[e,0]);   b[e,b[e,0]]:=f;
    inc(b[f,0]);   b[f,b[f,0]]:=e;
  end;
h:=0;   t:=1;
queue[t,1]:=s1;
queue[t,2]:=s2;
used[s1,s2]:=true;
d:=0;
while (h<t) or (d>0) do
  begin
    inc(h);
    e:=queue[h,1];
    f:=queue[h,2];
    if (e=0) and (f=0) then dec(h);
    if (r[h]>r[h-1]) or (h=t) then
      begin
        for i:=1 to d do
          begin
            inc(t);
            queue[t]:=queue2[i];
            r[t]:=r[h]+1;
          end;
        d:=0;
      end;
    for i:=1 to b[e,0] do
      if (not used[b[e,i],f]) and (b[e,i]<>f)and a[b[e,i],f]  then
        begin
          inc(t);
          r[t]:=r[h]+1;
          queue[t,1]:=b[e,i];
          queue[t,2]:=f;
          pr[b[e,i],f,1]:=e;
          pr[b[e,i],f,2]:=f;
          used[b[e,i],f]:=true;
        end;
    for i:=1 to b[f,0] do
      if (not used[e,b[f,i]]) and (b[f,i]<>e)and a[e,b[f,i]] then
        begin
          inc(t);
          r[t]:=r[h]+1;
          queue[t,1]:=e;
          queue[t,2]:=b[f,i];
          pr[e,b[f,i],1]:=e;
          pr[e,b[f,i],2]:=f;
          used[e,b[f,i]]:=true;
        end;
    for i:=1 to b[e,0] do
      for j:=1 to b[f,0] do
        if not used[b[e,i],b[f,j]] and (b[e,i]<>b[f,j]) and
          dif(e,b[e,i],f,b[f,j]) and a[b[e,i],b[f,j]] then
            begin
              inc(d);
              queue2[d,1]:=b[e,i];
              queue2[d,2]:=b[f,j];
              pr[b[e,i],b[f,j],1]:=e;
              pr[b[e,i],b[f,j],2]:=f;
              used[b[e,i],b[f,j]]:=true;
            end;
  end;
rec(f1,f2,0,0);
end.