#include <fstream>
#include <list>
#include <algorithm>
#include <queue>
#include <iterator>

using namespace std;

ifstream f("bfs.in");
ofstream g("bfs.out");

constexpr int maxSize = 100001;

class Graph {

    list <int>* adjacencyLists;
    int nrNodes;
    bool isDirected;

public:
    Graph();
    Graph(int, bool);
    ~Graph();

    void readEdges(int);
    void printDistanceToNode(int);
    void BFS(int, int[]);

};

Graph::Graph() {
    nrNodes = maxSize;
    isDirected = false;
    adjacencyLists = new list <int>[nrNodes];
}

Graph::Graph(int size, bool isDirected = false) {
    nrNodes = size;
    this->isDirected = isDirected;
    adjacencyLists = new list <int>[nrNodes];
}

Graph::~Graph() {
    delete[] adjacencyLists;
}


/// <summary>
/// reads a number of edges given as parameter
/// </summary>
void Graph::readEdges(int nrEdges) {
    int inNode, outNode;
    for (int i = 0; i < nrEdges; i++) {
        f >> outNode >> inNode;
        adjacencyLists[--outNode].push_back(--inNode);

        //if graph is not directed we also need a return edge
        if (!isDirected) {
            adjacencyLists[--inNode].push_back(--outNode);
        }
    }
}

/// <summary>
/// Prints the distance from a node given as parameter to all nodes in the graph, or -1 if they are inaccesible.
/// </summary>
/// <param name="startNode">The node for which distances are calculated</param>
void Graph::printDistanceToNode(int startNode) {

    int* distancesArray = new int[nrNodes];
    fill_n(distancesArray, nrNodes, -1);    //by filling distancesArray with -1 we assume that all nodes are inaccesible
    distancesArray[startNode] = 0;          //distance from starting node to starting node is 0
    BFS(startNode, distancesArray);

    // iterate through distance array and print
    for (int i = 0; i < nrNodes; i++)
        g << distancesArray[i] << " ";
}


/// <summary>
/// Does a breadth-first search and maps the distances to an array given as parameter.
/// </summary>
/// <param name="startNode"> starting node of search </param>
/// <param name="distancesArray"> array to map distances to </param>
void Graph::BFS(int startNode, int distancesArray[]) {
    queue<int> toVisit;
    toVisit.push(startNode);

    while (toVisit.empty() != true) {
        int currentNode = toVisit.front();
        int currentDistance = distancesArray[currentNode];
        toVisit.pop();

        /// iterate through the current node's neighbours
        for (auto nodeIt = adjacencyLists[currentNode].begin(); nodeIt != adjacencyLists[currentNode].end(); nodeIt++)
            if (distancesArray[*nodeIt] == -1) {
                toVisit.push(*nodeIt);
                distancesArray[*nodeIt] = currentDistance + 1;
            }

    }
}

int n, m, s;
int main()
{
    f >> n >> m >> s;
    Graph graf(n, true);
    graf.readEdges(m);
    graf.printDistanceToNode(--s);
}