#include<iostream>
#include<fstream>

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

struct nod
        {
        int a;
        nod *next;
        }*t[100010];

int s,n,r,end,m,i,j,b[16010],c[1000010];

void parcurg()
        {

        nod *q;
        while(r<=end)
                {
                q=t[c[r]];
                while(q!=NULL)
                        {
                        if(b[q->a]==0&&q->a!=s)
                        {
                        c[end]=q->a;
                        b[c[end]]=b[c[r]]+1;
                        end++;
                        }
                        q=q->next;
                        }
                r++;
                }
        }


int main()
{
f>>n>>m>>s;

while(m>0)
        {
        f>>i>>j;
        nod *q;
        q=new nod;
        q->a=j;
        q->next=t[i];
        t[i]=q;
        m--;
        }

r=1;
c[r]=s;
end=r+1;
parcurg();

for(i=1;i<=n;i++)
if(i==s)g<<0<<' ';
else
if(b[i]==0)g<<-1<<' ';
else g<<b[i]<<' ';

g.close();
return 0;
}