#include <stdio.h>
#include <vector>
//#define MAXN 100000

using namespace std;

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

const int MAXN=100000;
int n,m,coada[MAXN],viz[MAXN],s;
vector <int> muchii[MAXN];

void citire()
{
    freopen("bfs.in","r",stdin);
    //f>>n>>m>>s;
    scanf("%d%d%d",&n,&m,&s);
    for (int i=1;i<=m;i++)
    {
        int x,y;
        //f>>x>>y;
        scanf("%d%d",&x,&y);
        muchii[x].push_back(y);
    }
}

void bf(int s)
{
    int p,u,i,x;
    p=0;
    u=1;
    for (i=1;i<=n;i++)
      viz[i]=-1;
    coada[u]=s;
    viz[s]=0;
    while(p!=u)
    {
        p++;
        x=coada[p];
        for(i=0;i<muchii[x].size();i++)
        {
            if(viz[muchii[x][i]]==-1)
            {
                u++;
                coada[u]=muchii[x][i];
                viz[muchii[x][i]]=viz[x]+1;
            }
        }
    }
}

void scriere()
{
    freopen("bfs.out","w",stdout);
    for(int i=1;i<=n;i++)
     //g<<viz[i]<<" ";
     printf("%d ",viz[i]);
}
int main()
{
    citire();
    bf(s);
    scriere();
    return 0;
}