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

using namespace std;

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

constexpr int maxSize = 100001;

class Graph {

    vector<vector<int>> adjacencyLists;
    int nrNodes;
    bool isDirected;

public:
    Graph(int, bool);
    void initializeAdjacencyLists();

    void readEdges(int);
    void printDistancesToNode(int);
    void BFS(int, vector<int>&);

};

Graph::Graph(int size = maxSize, bool isDirected = false) {
    nrNodes = size;
    this->isDirected = isDirected;
    initializeAdjacencyLists();
}


/// <summary>
/// initializes empty adjacency lists (vectors)
/// </summary>
void Graph::initializeAdjacencyLists() {
    for (int i = 0; i < nrNodes; i++) {
        vector<int> emptyAdjacencyVector;
        adjacencyLists.push_back(emptyAdjacencyVector);
    }
}

/// <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;

        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::printDistancesToNode(int startNode) {

    vector<int> distancesArray(nrNodes, -1);
    distancesArray[startNode] = 0;          //distance from starting node to starting node is 0
    BFS(startNode, distancesArray);

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


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

    // while there still are accesible nodes that were not visited
    while (toVisit.empty() != true) {
        currentNode = toVisit.front();
        /// iterate through the current node's neighbors
        for (int neighboringNode : adjacencyLists[currentNode])
            if (distancesArray[neighboringNode] == -1) {
                toVisit.push(neighboringNode);
                distancesArray[neighboringNode] = distancesArray[currentNode] + 1;
            }
        toVisit.pop();
    }
}

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