#include <fstream>
#include <queue>
#include <bitset>

using namespace std;

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


struct node
{
    int value;
    int dist;
    node *next;
};

int n,m,nod;
node *L[100010],*Q;
bitset<100010>viz;
vector<int>ans(100010,0);

void add_begin(node *&L,int integer,int dist)
{
    node *l= new node;
    l->value=integer;
    l->dist=dist;
    l->next=L;
    L=l;
}

void delete_end(node *&L)
{
    if(L->next==nullptr)
    {
        L=nullptr;
        return;
    }
    node *l=L;
    while(l->next->next!=nullptr)
        l=l->next;

    node * last_node = l->next;
    l->next=nullptr;
    free(last_node);
}


int main() {
    fin>>n>>m>>nod;

    add_begin(Q,nod,0);
    Q->dist=0;

    for(;m;m--)
    {
        int x,y;
        fin>>x>>y;
        add_begin(L[x],y,0);
    }

    while(Q!=nullptr)
    {
        int current_node = (*Q).value;
        int dist=Q->dist;
        ans[current_node]=dist;
        viz[current_node]=1;
        while(L[current_node]!=nullptr)
        {
            if(!viz[L[current_node]->value])
            {
                viz[L[current_node]->value]=1;
                add_begin(Q,L[current_node]->value,(L[current_node]->dist)+1);
            }
            L[current_node]=L[current_node]->next;
        }

        delete_end(Q);
    }

    for(int i=1;i<=n;i++)
        fout<<ans[i]<<" ";

    return 0;
}