#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<pair<int, int>> toCompute;
    toCompute.push({ startNode, 0 });

    while (toCompute.empty() != true) {
        int currentNode = toCompute.front().first;
        int currentDistance = toCompute.front().second;
        toCompute.pop();

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

    }
}

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