program df;
const fi='bfs.in';
      fo='bfs.out';
var a:array of array of longint;
   bufin,bufout:array[1..65000] of longint;
   x,niv,viz:array of longint;
   v:array[1..100000] of longint;
   f,g:text;
   n,m,ns,i,t,y,st,sf:longint;
begin
assign(f,fi);
reset(f);
assign(g,fo);
rewrite(g);
settextbuf(f,bufin);
settextbuf(g,bufout);
read(f,n,m,ns);
setlength(a,n+1,1);
setlength(viz,n+1);
setlength(x,n+1);
setlength(niv,n+1);
for i:=1 to m do
   begin
   read(f,t,y);
   inc(a[t,0]);
   setlength(a[t],a[t,0]+1);
   a[t,a[t,0]]:=y;
   end;
   st:=0;
   sf:=1;
  x[sf]:=ns;

  viz[ns]:=1;

  for i:=1 to n do
  v[i]:=-1;
   v[ns]:=0;
  while st<sf do
    begin
    inc(st);
    for i:=1 to a[x[st],0] do
       begin
         if viz[a[x[st],i]]=0 then
            begin
            inc(sf);
            x[sf]:=a[x[st],i];
            viz[a[x[st],i]]:=1;
            niv[sf]:=niv[st]+1;
            v[a[x[st],i]]:=niv[sf];
            writeln(a[x[st],i]);
            end;
       end;
    end;
    writeln;
    for i:=1 to n do
      write(g,v[i],' ');
      close(f);
      close(g);
      end.