#include <iostream>
#include <fstream>

using namespace std;

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

struct graf{
int nod;
int dist;
graf* next;
};

graf* v[100001];
int cost[100001];
bool vis[100001];
int q[100001];
int a=1,b=1;
int c;

void add(int a, int b, int cost)
{
    graf* q = new graf;
    q->nod  = b;
    q->next = v[a];
    v[a] = q;
}

int BFS(int k){
    ++c;
    graf*  p;
    for(p = v[k]; p!=NULL; p=p->next){
        if(vis[p->nod] == 0)
            ++b,
            vis[p->nod] = 1,
            q[b] = p->nod,
            cost[p->nod] = c;
    }
    ++a;

    if(b < a)
        return -1;
    else
        BFS(q[a]);

}

int main()
{
    int i,x,y;
    int n,m,s;
    int time;
    fin >> n >> m >> s;
    time = n;

    for(i=1;i<=n;++i)
        cost[i] = -1;
    cost[s] = 0;

    for(i=1;i<=m;++i){
    fin >> x >> y;
    add(x,y,1);
    }

    vis[s] = 1;
    q[1] = s;

    BFS(s);
    for(i=1;i<=n;++i)
        cout << cost[i] << " ";



    return 0;
}