#include <cstdio>
#include <vector>
#include <stdio.h>
#include <string.h>

using namespace std;

char s[20];
int pass[100001];

struct pereche
{
    int nod,distanta;
};

vector <int> muchii[100001];
vector <pereche>BFS;

int main()
{
    freopen("bfs.in","r",stdin);
    freopen("bfs.out","w",stdout);
    int n,m,S;
    scanf("%d %d %d\n",&n,&m,&S);
    for (int i=1;i<=m;++i)
    {
        gets(s);

        int A=0,B=0;

        bool a=0;
        for (int j=0;s[j]!=0;++j)
        {
            if (s[j]==' ') a=1;
            else
            {
                if (a==0) A=A*10+s[j]-'0';
                if (a==1) B=B*10+s[j]-'0';
            }
        }
        muchii[A].push_back(B);
    }
    memset(pass,0xff,sizeof(pass));

    pass[S]=0;
    int cnt=0;

    int l=muchii[S].size();
    for (int i=0;i<l;++i)
        BFS.push_back({muchii[S][i],1});

    while (cnt+1<=BFS.size())
    {
        int x=pass[BFS[cnt].nod];
        if (pass[BFS[cnt].nod]==-1 || pass[BFS[cnt].nod]>BFS[cnt].distanta)
        {
            pass[BFS[cnt].nod]=BFS[cnt].distanta;
            int l=muchii[BFS[cnt].nod].size();

            for (int i=0;i<l;++i)
            {
                if (pass[muchii[BFS[cnt].nod][i]]==-1)
                    BFS.push_back({muchii[BFS[cnt].nod][i],BFS[cnt].distanta+1});
                if (pass[muchii[BFS[cnt].nod][i]]>BFS[cnt].distanta+1)
                    BFS.push_back({muchii[BFS[cnt].nod][i],BFS[cnt].distanta+1});
            }
        }
        cnt++;
    }
    for (int i=1;i<=n;i++)
        printf("%d ",pass[i]);
}