#include <vector>
#include <stack>
#include <iostream>
#include <cstring>
#include <utility>
#include <fstream>
#include <queue>



std::ifstream fileOpen("bfs.in");
std::ofstream fileOut("bfs.out");


class Graph
{
  
// #pragma region declarations
    int numberOfElements;
    std::vector<int> adjacentList[100000];
    int visitedNodes[100000];
    
// #pragma endregion

// #pragma region "secret" functions
    void flushVisited();
// #pragma endregion

public:

// #pragma region constructors
    Graph(int numberOfElements);
// #pragma endregion

// #pragma region functions
    void addEdge(int a, int b);
    void printGraph();
    void dfsRec(int node);
    void dfsIter(int node);
    void bfs(int node);
// #pragma endregion

};

// #pragma region functions related to the class
void Graph::addEdge(int a, int b)
{
    if (a != b)
    {
        adjacentList[a].push_back(b);
    }
}

void Graph::printGraph() {
    for(int node = 1; node <= numberOfElements; node++) {
        std::cout << "Nodul " << node << " are lista:";
        for(auto x : adjacentList[node]) {
            std::cout << "->" << x;
        }
        std::cout << "\n";
    }
}

// void Graph::dfsRec(int node) {
//     // Rec for recursive method
//     if(visitedNodes[node] == 1){
//         return;
//     }
//     visitedNodes[node] = 1;
//     std::cout << node << " ";
//     for(int adjacentNode : adjacentList[node]) {
//         dfsRec(adjacentNode);
//     }
// }

// void Graph::dfsIter(int node) {
//     std::stack<int> nodeStack;
//     // flush the array
//     flushVisited();
//     // 1. push the node
//     nodeStack.push(node);
//     visitedNodes[node] = 1;
//     // std::cout << node << " ";

//     // 2. Iterate through the adjacentList 
//     while(!nodeStack.empty()){
//         // verify the top and then pop it.
//         int top = nodeStack.top();
//         if(visitedNodes[top] == 0) {
//             // std::cout << top << " ";
//             visitedNodes[top] = 1;
//         }
//         nodeStack.pop();

//         for(int theOtherNodes : adjacentList[top]) {
//             if(visitedNodes[theOtherNodes] == 0) {
//                 nodeStack.push(theOtherNodes);  
//             }
//         }
//     }

// }

// void Graph::bfs(int node) {
//     std::queue<std::pair<int, int>> nodeQueue;
//     int distance[5000] = {0};
//     flushVisited();

//     nodeQueue.push({node, 0});
//     visitedNodes[node] = 1;
//     std::cout << node << " ";

//     while(!nodeQueue.empty()) {
//         int front = nodeQueue.front().first;
//         int distanta = nodeQueue.front().second;         
//         // std::cout << front << " ";
//         visitedNodes[front] = 1;
//         nodeQueue.pop();
//         distance[front] = distanta + 1;
//         for(int theOtherNodes : adjacentList[front]) {
//             if(visitedNodes[theOtherNodes] == 0) {
//                 nodeQueue.push({theOtherNodes, distanta + 1});
//             }
//         }
//     }
//     std::cout << "\n";
    
//     // After the BFS you output the elements of distance[i];
//     for(int index = 0; index < numberOfElements; index++) {
//         // std::cout << distance[index] << std::endl;
//         if(distance[index] != 0) {
//             std::cout << distance[index] << " ";
//         }
//         else {
//             std::cout << -1 << " ";
//         }
//     }
// }

void Graph::bfs(int node) {

    int distance[100000] = {0};

    flushVisited();

    std::queue<int> nodeQueue;
    visitedNodes[node] = 1;
    nodeQueue.push(node);

    while(!nodeQueue.empty()) {
        int front = nodeQueue.front();
        nodeQueue.pop();

        for(auto theOtherNodes : adjacentList[front]) {
            if(visitedNodes[theOtherNodes] == 0) {
                visitedNodes[theOtherNodes] = 1;
                nodeQueue.push(theOtherNodes);
                distance[theOtherNodes] = distance[front] + 1;
            }
        }
    }
    for(int i = 0; i < numberOfElements; i++) {
        if(visitedNodes[i] != 0) {
            fileOut << distance[i] << " ";
        }
        else {
            fileOut << -1 << " ";
        }
    }
}

void Graph::flushVisited() {
    std::memset(visitedNodes, 0, 100000);
}

Graph::Graph(int numberOfElements) : numberOfElements(numberOfElements) {
    flushVisited();
    
}
// #pragma endregion

int main() 
{

    int nodes, edges, source;

    fileOpen >> nodes >> edges >> source;
    
    Graph bfsGraph(nodes);

    int x, y;

    while(fileOpen >> x >> y) {
        bfsGraph.addEdge(x - 1, y - 1);
    }

    bfsGraph.bfs(source - 1);
    
    return 0;
}