#include <map>
#include <queue>
#include <vector>
#include <iostream>
#include <fstream>

using namespace std;

struct Node {

    int data;
    Node* next;
};


class LinkedList {
private:
    Node* first;

public:

    LinkedList() : first( nullptr ) {}

    void insertAtBeginning( const int value ) {

        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = first;
        first = newNode;
    }

    void insertAtEnd(const int value) {

        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = nullptr;

        if ( !first ) {  // if list is empty

            first = newNode;
            return;
        }

        Node* temp_node = first;
        while (temp_node->next)
            temp_node = temp_node->next;

        temp_node->next = newNode;
    }

    void insertAtPosition( const int value, int position ) {

        if ( position < 1 ) {

            std::cout << "Position should be >= 1." << endl;
            return;
        }

        if ( position == 1 ) {

            insertAtBeginning(value);
            return;
        }

        Node* newNode = new Node();
        newNode->data = value;


        Node* temp = first;
        for (int i = 1; i < position - 1 && temp; ++i)
            temp = temp->next;


        if ( !temp ) {

            cout << "Position out of range." << endl;
            delete newNode;
            return;
        }

        newNode->next = temp->next;
        temp->next = newNode;
    }


    void deleteFromBeginning() {

        if ( !first ) {

            cout << "List is empty." << endl;
            return;
        }

        Node* temp_node = first;
        first = first->next;
        delete temp_node;
    }


    void deleteFromEnd() {
        if ( !first ) {

            cout << "List is empty." << endl;
            return;
        }

        if ( !first->next ) {

            delete first;
            first = nullptr;
            return;
        }


        Node* temp = first;
        while ( temp->next->next )
            temp = temp->next;


        delete temp->next;
        temp->next = nullptr;
    }


    void deleteFromPosition(int position) {

        if (position < 1) {

            cout << "Position should be >= 1." << endl;
            return;
        }

        if ( position == 1 ) {

            deleteFromBeginning();
            return;
        }

        Node* temp = first;
        for (int i = 1; i < position - 1 && temp; ++i)
            temp = temp->next;


        if (!temp || !temp->next) {
            cout << "Position out of range." << endl;
            return;
        }

        Node* nodeToDelete = temp->next;
        temp->next = temp->next->next;
        delete nodeToDelete;
    }


    void display() const {

        if ( !first ) {

            cout << "List is empty." << endl;
            return;
        }

        const Node* temp_node = first;

        while (temp_node) {

            cout << temp_node->data << " -> ";
            temp_node = temp_node->next;
        }

        cout << "NULL" << endl;
    }

    [[nodiscard]] Node * getFirst() const {
        return first;
    }
};


int main() {

    // map intre int si LinkedList
    ifstream f( "bfs.in" );
    ofstream g( "bfs.out" );

    map< int, LinkedList> d;

    int n, m, i, x, y, s;
    f >> n >> m >> s;

    for( i = 1; i <= m; i++ ) {

        f >> x >> y;
        d[ x ].insertAtEnd(y);
    }

    // print la graf
    // for( i = 1; i <= n; i++ ) {
    //
    //     cout << i << " : ";
    //     d[ i ].display();
    //     cout << '\n';
    // }

    queue<int> q;
    vector<bool> visited( n + 1, false );
    vector<int> distance( n + 1, -1 );

    q.push( s );
    distance[ s ] = 0;
    int nod_curent;

    while( !q.empty() ) {

        nod_curent = q.front();
        q.pop();

        visited[ nod_curent ] = true;
        Node* temp_node = d[ nod_curent ].getFirst();

        while( temp_node ) {

            if( !visited[ temp_node->data ] ) {

                q.push( temp_node->data );
                visited[ temp_node->data ] = true;
                distance[ temp_node->data ] = distance[ nod_curent ] + 1;
            }

            temp_node = temp_node->next;
        }

    }

    for( i = 1; i <= n; i++ )
        g << distance[ i ] << ' ';
    g << '\n';

}