#include <bits/stdc++.h>
using namespace std;

ifstream fin("bfs.in");
ofstream fout("bfs.out");

struct nod{int info;
            nod *urm;}*v[100001];
vector <int> viz;
queue <int> C;

int main()
{
    int n, x, m, a, b;
    fin>>n>>m>>x;
    viz.resize(n+1);
    while(m)
    {
       fin>>a>>b;
       if(v[a] == NULL)
       {
           v[a]=new nod;
           v[a] -> urm = NULL;
           v[a] -> info = b;
       }
       else
       {
           nod *q, *g;
           g=v[a];
           while(g->urm != NULL)
            g=g->urm;
           q=new nod;
           q->info = b;
           q->urm = NULL;
           g->urm = q;
       }
       m--;
    }

    C.push(x);
    viz[x]=1;
    while(! C.empty())
    {
        nod *p;
        for(p=v[C.front()]; p!=NULL; p=p->urm)
         if(viz[p->info] == 0)
         {
            viz[p->info]=viz[C.front()]+1;
            C.push(p->info);
         }
        C.pop();
    }

    for(int i=1; i<=n; i++)
        fout<<viz[i]-1<<" ";
    return 0;
}