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

using namespace std;

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

void bfs(const vector<vector<int>> &adj, const int start, vector<int> &eredmeny)
{
    int count = 0;
    eredmeny[start] = count;

    vector<bool> visited(adj.size());
    queue<int> q;   

    visited[start] = 1;
    q.push(start);

    while(!q.empty())
    {
        int current = q.front();
        q.pop();

        bool tovabb = 0;

        for(int i : adj[current])
        {
            if(!visited[i])
            {
                eredmeny[i] = count + 1;
                visited[i] = 1;
                q.push(i);

                tovabb = 1;
            }
        }

        if(tovabb)
        {
            count++;
        }
    }
}

int main()
{
    int n, m, s;
    be >> n >> m >> s;

    vector<vector<int>> adj(n + 1);

    int x, y;

    for(int i = 0; i < m; i++)
    {
        be >> x >> y;
        adj[x].push_back(y);
    }

    vector<int> eredmeny(n + 1, -1);

    bfs(adj, s, eredmeny);

    for(int i = 1; i <= n; i++)
    {
        ki << eredmeny[i] << " ";
    }

    return 0;
}