#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int n, m, s, lvl[100003], x, y, q[100003];
vector<int> v[100003];

void bfs()
{
    vector<int> :: iterator it;
    int cs = 1, ci = 2;
    q[cs] = s;
    lvl[s] = 0;
    while(cs <= ci)
    {
        x = q[cs];
        cs ++;
        for(it = v[x].begin(); it != v[x].end(); ++ it)
            if(lvl[*it] == -1)
            {
                q[ci++] = *it, lvl[*it] = lvl[x] + 1;
            }
    }
}

int main()
{
    F >> n >> m;
    F >> s;
    for(int i = 0; i < m; ++ i)
    {
        F >> x >> y;
        v[x].push_back(y);
    }
    for(int i = 1; i <= n; ++ i)
        lvl[i] = -1;
    lvl[s] = 0;
    bfs();
    for(int i = 1; i <= n; ++ i)
        G << lvl[i] << " ";
    return 0;
}