#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
int m, n, x, y, k, vizitat[100010], ok, i, j;
vector<vector<int>> mat;
queue <int> insane;
int main()
{
    in >> n >> m >> k; ok=k;
    mat.resize(n+4);
    for (i = 1; i <= m; i++)
    {
        in >> x >> y;
        mat[x].push_back(y);
    }
    for (i = 1; i <= n; i++)
        sort(mat[i].begin(), mat[i].end());
    insane.push(k);
    vizitat[k] = 1;
    while(insane.size())
    {
        k = insane.front();
        for (auto ind : mat[k])
        {
            if (vizitat[ind] == 0)
            {
                insane.push(ind);
                vizitat[ind] = vizitat[k]+1;
            }
        }
        insane.pop();
    }
    for (i = 1; i <= n; i++)
        out << vizitat[i]-1 << ' ';
    return 0;
}