#include <fstream>
#define NM 100005
using namespace std;
ifstream fin ("bfs.in");
ofstream fout ("bfs.out");
struct nod
{
    int val;
    nod* urm;
}*v[NM], *prim, *ult;
int n, m, dist[NM], S;
void adaugare_in_fata(nod*&prim, int x)
{
    nod* q = new nod;
    q->urm = NULL;
    q->val = x;
    if(prim == NULL)
        prim = q;
    else
    {
        q->urm = prim;
        prim = q;
    }
}
void adaugare_la_sf(nod*&ult, int x)
{
    nod* q = new nod;
    q->val = x;
    q->urm = NULL;
    if(ult == NULL)
        prim = ult = q;
    else
    {
        ult->urm = q;
        ult = q;
    }
}
void eliminare_prim(nod*&prim)
{
    if(prim == NULL)
        return ;
    nod* aux = prim;
    prim = prim->urm;
    delete aux;
}
bool goala(nod*prim)
{
    if(prim == NULL)
        return 1;
    return 0;
}
void read();
int main()
{
    read();
    adaugare_la_sf(ult, S);
    for(int i=1; i<=n; i++)
        dist[i] = INT_MAX;
    dist[S] = 1;
    while(!goala(prim))
    {
        int cur = prim->val;
        for(nod* i=v[cur]; i!=NULL; i=i->urm)
            if(dist[cur]+1 < dist[i->val])
            {
                dist[i->val] = dist[cur]+1;
                adaugare_la_sf(ult, i->val);
            }
        eliminare_prim(prim);
    }
    for(int i=1; i<=n; i++)
        if(dist[i] == INT_MAX)
            fout << -1 << ' ';
        else fout << dist[i]-1 << ' ';
    return 0;
}
void read()
{
    fin >> n >> m >> S;
    for(int i=1; i<=m; i++)
    {
        int x, y;
        fin >> x >> y;
        adaugare_in_fata(v[x], y);
    }
}