#include<fstream>
using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");
struct nod
{
    int varf;
    int leg;
};

struct nod T[1000009];
int n,m,S,k;
int vstart[100009], dist[100009],coada[100009];
void citire()
{
    int a,b;
    fin>>n>>m>>S;
    k=0;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b;
        k++;
        T[k].varf=b;
        T[k].leg=vstart[a];
        vstart[a]=k;
    }
}
void BFS()
{
    int pr,ul;
    for(int i=1;i<=n;i++)
    {
        dist[i]=-1;
    }
    coada[1]=S;
    pr=1;
    ul=1;
    dist[S]=0;
    while(pr<=ul)
    {
        int x=coada[pr];
        for(int i=vstart[x];i!=0;i=T[i].leg)
        {
           int y=T[i].varf;
            if(dist[y]==-1)
            {
                dist[y]=1+dist[x];
                ul++;
                coada[ul]=y;
            }
        }
        pr++;
    }
}
int main()
{
    citire();
    BFS();
    for(int i=1;i<=n;i++)
    {
        fout<<dist[i]<<" ";
    }
    fin.close();
    fout.close();
    return 0;
}