type vec=record
        a:array of -2..101000;
        end;

var     i,n,j,m,s,x,y,k:longint;
        v:array[0..101000]of vec;
        q,l:array[0..1100000]of -2..101000;
        ok:boolean;

begin
assign(input,'bfs.in');
assign(output,'bfs.out');

reset(input);
rewrite(output);



readln(n,m,s);

for i:=0 to n do
begin
setlength(v[i].a,1);
v[i].a[0]:=-1;
end;


for i:=1 to m do
begin
        readln(x,y);
        inc(l[x]);
        setlength(v[x].a,l[x]+1);
        ok:=true;

        for j:=1 to l[x] do
                if v[x].a[j]=y then
                ok:=false;
        if ok then
        v[x].a[l[x]]:=y;
end;


v[s].a[0]:=0;

i:=0;
k:=1;
q[1]:=s;

while i<=m do
begin

        inc(i);

        for j:=1 to l[q[i]] do
        begin
                inc(k);
                if q[i]<>v[q[i]].a[j] then
                begin

                q[k]:=v[q[i]].a[j];

                if (v[q[k]].a[0]>v[q[i]].a[0]+1) or (v[q[k]].a[0]=-1) then
                v[q[k]].a[0]:=v[q[i]].a[0]+1;
                end;
        end;



end;


for i:=1 to n do
write(v[i].a[0],' ');

writeln;

for i:=1 to m do
write(v[1].a[i],' ');



close(output);

end.