#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

ifstream in("bfs.in");
ofstream out("bfs.out");
vector <int> a[100005], cost(100005, -1);
queue <int> q;

    int n, m, s, x, y;
int main()
{
    in >> n >> m >> s;
    cost [ s ]=0;
    q.push ( s );
    for(int i = 1;i <= m; ++i)
    {
        in >> x >> y;
        a[ x ].push_back( y );//arc de la x la y
    }
    in.close();
    while(!q.empty())
    {
        int b = q.back();
        for(unsigned int i=0; i < a[b].size() ; ++i)
            if(cost[a[b][i]]==-1)
            {
                cost[a[b][i]]=cost[b]+1;
                q.push ( a[b][i] );
            }
        q.pop();
    }
    for(int i=1;i<=n;++i)
        out<<cost[i]<<" ";
    out.close();
    return 0;
}