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

std::ifstream in("bfs.in");
std::ofstream out("bfs.out");

std::vector<std::vector<int>> adj(100001);
std::vector<int> v(100001, 0);
std::vector<int> d(100001, -1);
int main()
{
    int n, m, s;
    std::cin >> n >> m >> s;
    for ( int i = 1; i <= m; ++i )
    {
        int x, y;
        std::cin >> x >> y;
        adj[x].emplace_back(y);
    }
    v[s] = 1;
    d[s] = 0;
    std::queue<int> q;
    q.emplace(s);
    while ( !q.empty() )
    {
        auto nr = q.front();
        q.pop();
        for ( auto c:adj[nr] )
            if ( v[c] == 0 )
            {
                v[c] = 1;
                q.emplace(c);
                d[c] = d[nr] + 1;
            }
    }
    for ( int i = 1; i <= n; ++i )
    {
        std::cout << d[i] << "\n";
    }

    return 0;
}