#include <fstream>
#include <vector>
#include <deque>
#include <sstream>
#include <cstring>
using namespace std;

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

vector<int> g[100010];
deque<int> c;
int x,y,i,j,n,m,s,dist[100010];

string show(deque<int> x)
{
    stringstream s;
    s<<"[ ";
    for(deque<int>::iterator it=x.begin(); it!=x.end(); it++)
        s<<*it<<' ';
    s<<"]";
    return s.str();

}

int main()
{
    in>>n>>m>>s;
    for(i=1; i<=m; i++)
    {
        in>>x>>y;
        g[x].push_back(y);
    }
    
    c.push_back(s);
    memset(dist+1,-1,sizeof(dist[0])*n);
    dist[s] = 0;
    while(!c.empty())
    {
        s = c.front();c.pop_front();
        for(i=0; i<g[s].size(); i++)
            if(dist[g[s][i]] == -1)
                {c.push_back(g[s][i]);dist[g[s][i]]=dist[s]+1;}
    }
    for(i=1; i<=n; i++)
        out<<dist[i]<<' ';

    return 0;
}