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

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

vector<vector<int>> g;
queue<int> Q;
vector<bool> v;
int n, m , s;
vector<int> rez;
void Bf(int x);
void Read();

int main()
{
    Read();
    rez[s] = 0;
    Bf(s);
    for(int i = 1; i <= n; ++i )
           if(rez[i] == 0 )
                rez[i] = -1;
    rez[s] = 0;
    for(vector<int> ::iterator it = rez.begin()+1; it != rez.end(); ++it)
            os << *it << ' ';

    is.close();
    os.close();
    return 0;

}

void Read()
{
    is >> n;
    is >> m;
    is >> s;
    g = vector<vector<int>>(n+1);
    v = vector<bool>(n+1);
    rez = vector<int>(n+1);
    int x,y;
    for(int i = 1; i <= m; ++i)
    {
        is >> x >> y;
        g[x].push_back(y);
    }
    return;
}


void Bf(int x)
{
    Q.push(x);
    v[x] = true;
    //os << x << ' ';
    int i;
    while( !Q.empty() )
    {
        i = Q.front(); Q.pop();
        for(vector<int> ::iterator it = g[i].begin(); it != g[i].end(); ++it )
        {
            if( v[*it] ) continue;
            v[*it] = true;
            rez[*it] = rez[i] + 1;
            Q.push(*it);
        }
    }

}