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

ifstream In("bfs.in");
ofstream Out("bfs.out");
vector<int>* Neighbours;
queue<int> Queue;
int* Cost;
int NodesNo;
int EdgesNo;
int Start;

void alloc()
{
    Neighbours = new vector<int>[NodesNo];
    Cost = new int[NodesNo];

    memset(Cost, -1, sizeof(int) * NodesNo);
}

void dealloc()
{
    delete[] Neighbours;
    delete[] Cost;
}

void init()
{
    --Start;
}

void readData()
{
    In >> NodesNo >> EdgesNo >> Start;
    alloc();
    init();

    for (int i = 0, x, y; i != EdgesNo; ++i)
    {
        In >> x >> y;
        Neighbours[x - 1].push_back(y - 1);
    }

    In.close();
}

void printData()
{
    for (int i = 0; i != NodesNo; ++i)
        Out << Cost[i] << " ";

    Out.close();
}

void addToQueue(const int& node)
{
    Queue.push(node);
}

int removeFromQueue()
{
    int node = Queue.front();
    Queue.pop();

    return node;
}

void solve(const int& start)
{
    Cost[start] = 0;
    addToQueue(start);

    while (!Queue.empty())
    {
        int node = removeFromQueue();

        for (vector<int>::iterator it = Neighbours[node].begin(); it != Neighbours[node].end(); ++it)
            if (Cost[*it] == -1)
            {
                addToQueue(*it);
                Cost[*it] = Cost[node] + 1;
            }
    }
}

int main()
{
    readData();
    solve(Start);
    printData();
    dealloc();

    return 0;
}