{$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..101,0..101] of boolean;
pr: array[0..101,0..101,1..2] of integer;
queue: array[0..1000000,1..2] of integer;
n,m,s1,s2,f1,f2: integer;

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

var
i,e,f,h,t: 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;
  end;
h:=0;   t:=1;
queue[t,1]:=s1;
queue[t,2]:=s2;
used[s1,s2]:=true;
while h<t do
  begin
    inc(h);
    e:=queue[h,1];
    f:=queue[h,2];
    for i:=1 to n do
      if a[e,i] and (not used[i,f]) and (i<>f) then
        begin
          used[i,f]:=true;
          inc(t);
          queue[t,1]:=i;
          queue[t,2]:=f;
          pr[i,f,1]:=e;
          pr[i,f,2]:=f;
        end;
    for i:=1 to n do
      if a[f,i] and (not used[e,i]) and (i<>e) then
        begin
          used[e,i]:=true;
          inc(t);
          queue[t,1]:=e;
          queue[t,2]:=i;
          pr[e,i,1]:=e;
          pr[e,i,2]:=f;
        end;
  end;
rec(f1,f2,0);
end.