#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream is ("bfs.in");
ofstream os ("bfs.out");

const int INF = 0x3f3f3f3f;

int N, M, Source, Dist[100001];
vector <int> Graph[100001];
queue <int> Q;


void Read();
void BFS(int S);


int main()
{
    Read();
    BFS(Source);

    for (int i = 1; i <= N; ++i)
        if (Dist[i] == INF)
            os << "-1 ";
        else
            os << Dist[i] << ' ';

    is.close();
    os.close();
}

void Read()
{
    is >> N >> M >> Source;
    for (int i = 1, a, b; i <= M; ++i)
    {
        is >> a >> b;
        Graph[a].push_back(b);
    }
    for (int i = 1; i <= N; ++i)
        Dist[i] = INF;
};

void BFS(int S)
{
    Q.push(S);
    Dist[S] = 0;
    for (int i; !Q.empty(); )
    {
        i = Q.front();
        Q.pop();
        for (const int& j : Graph[i])
            if (Dist[j] > Dist[i] + 1)
                Dist[j] = Dist[i] + 1, Q.push(j);
    }
};