#include <fstream>
#include <unordered_set>
#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<unordered_set<int>> adjacencyLists;
    int nrNodes;
    bool isDirected;

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

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


};

Graph::Graph() {
    nrNodes = maxSize;
    isDirected = false;
    initializeAdjacencyLists();
}

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


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

}

/// <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].insert(--inNode);

        //if graph is not directed we also need a return edge
        if (!isDirected) {
            adjacencyLists[--inNode].insert(--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) {

    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 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) {
    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 neighboringNode : adjacencyLists[currentNode])
            if (distancesArray[neighboringNode] == -1) {
                toVisit.push(neighboringNode);
                distancesArray[neighboringNode] = currentDistance + 1;
            }
    }
}

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