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

using namespace std;

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

#define MAXN 100005
int n, m, start, used[MAXN];
vector <int> list[MAXN];

void read()
{
    int x, y;
    fin >> n >> m >> start;
    for (int i = 1; i <= m; i++)
        fin >> x >> y,
            list[x].push_back(y);
}
void BFS()
{
    queue <int> q;
    q.push(start);
    used[start] = 1;
    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        for (int i = 0; i < list[node].size(); i++)
            if (!used[list[node][i]])
                q.push(list[node][i]),
                       used[list[node][i]] = used[node] + 1;
    }
}

int main()
{
    read();
    BFS();
    for (int i = 1; i <= n; i++)
        fout << used[i] - 1 << " ";
    return 0;
}