#include <istream>
#include <stdexcept>
#include <iostream>

// +-------------------------------------------------------------------------------------------------------------------+
// |  src/graph/base/BasicGraph.hpp                                                                                    |
// +-------------------------------------------------------------------------------------------------------------------+
namespace graph {

class BasicGraph;
class BasicGraphNode;
class BasicBreadthFirstSearchResults;
class BasicDepthFirstSearchResults;

class BasicGraphEdge {
protected:
    BasicGraph* graph;
    BasicGraphNode* src;
    BasicGraphNode* dst;
public:
    BasicGraphEdge(BasicGraph* graph, BasicGraphNode* src, BasicGraphNode* dst);

    BasicGraph* GetGraph() const;
    BasicGraphNode* GetSource() const;
    BasicGraphNode* GetDestination() const;
    BasicGraphNode* GetOpposite(const BasicGraphNode* node) const;
};


class BasicGraphEdgeArray {
private:
    BasicGraphEdge** edges;
    int size;
    int capacity;

    void Alloc(int capacity);
public:
    BasicGraphEdgeArray();

    BasicGraphEdge* operator [](const int &i) const;

    int Size() const;
    BasicGraphEdgeArray &AddEdge(BasicGraphEdge* edge);

    void Clear();

    BasicGraphEdge** begin() const;
    BasicGraphEdge** end() const;
};


class BasicGraphNode {
protected:
    int id;
    BasicGraph* graph;
    BasicGraphEdgeArray incoming;
    BasicGraphEdgeArray outgoing;
public:
    BasicGraphNode(BasicGraph* graph, int id);

    BasicGraphNode& AddIncomingEdge(BasicGraphEdge* edge);
    BasicGraphNode& AddOutgoingEdge(BasicGraphEdge* edge);

    const BasicGraphEdgeArray *GetIncomingEdges() const;
    const BasicGraphEdgeArray *GetOutgoingEdges() const;

    int GetId() const;
};


class BasicGraph {
protected:
    bool initialized;
    int numNodes;
    BasicGraphNode** nodes;
    BasicGraphEdgeArray edges;

    BasicGraph& Init(int numNodes);

    BasicGraphNode* GetNode(const int &index) const;
public:
    BasicGraph();
    explicit BasicGraph(int numNodes);

    ~BasicGraph();

    int Size() const;

    virtual bool IsDirected() const = 0;
    virtual BasicGraph& AddEdge(const int &src, const int &dst) = 0;

    BasicBreadthFirstSearchResults BreadthFirstSearch(const int &src) const;
    BasicBreadthFirstSearchResults FullBreadthFirstSearch() const;

    BasicDepthFirstSearchResults DepthFirstSearch(const int &src) const;
    BasicDepthFirstSearchResults FullDepthFirstSearch() const;

    friend std::istream &operator >>(std::istream &in, BasicGraph &g);
    friend std::ostream &operator <<(std::ostream &out, BasicGraph &g);
};

}


// +-------------------------------------------------------------------------------------------------------------------+
// |  src/graph/base/src/graph/base/algorithms/breadth-first-search/BreadthFirstSearchResults.hpp                      |
// +-------------------------------------------------------------------------------------------------------------------+
namespace graph {

class BasicGraph;
class BasicGraphNode;
class BasicGraphEdge;

class BasicBreadthFirstSearchResults {
private:
    const BasicGraph* graph;
    int* distances;
    int* parents;
    int* roots;

    void Run(const BasicGraphNode* node);
    void Extend(const BasicGraphNode* node=nullptr, const BasicGraphNode* parent=nullptr, const BasicGraphEdge* edge=nullptr);
public:
    explicit BasicBreadthFirstSearchResults(const BasicGraph* graph);
    BasicBreadthFirstSearchResults(const BasicBreadthFirstSearchResults &other);

    ~BasicBreadthFirstSearchResults();

    int GetRoot(const int &nodeId) const;
    int GetParent(const int &nodeId) const;
    int GetDistance(const int &nodeId) const;
    bool IsReachable(const int &nodeId) const;

    friend class BasicGraph;
};

}


// +-------------------------------------------------------------------------------------------------------------------+
// |  src/graph/base/src/graph/base/algorithms/breadth-first-search/DepthFirstSearchResults.hpp                        |
// +-------------------------------------------------------------------------------------------------------------------+
namespace graph {

class BasicGraph;
class BasicGraphNode;
class BasicGraphEdge;

class BasicDepthFirstSearchResults {
private:
    const BasicGraph* graph;
    int* parents;
    int* roots;

    void Extend(const BasicGraphNode* node, const BasicGraphNode* parent, const BasicGraphEdge* edge);
    void Run(const BasicGraphNode* node, const BasicGraphNode* parent=nullptr, const BasicGraphEdge* edge=nullptr);
public:

    explicit BasicDepthFirstSearchResults(const BasicGraph* graph);
    BasicDepthFirstSearchResults(const BasicDepthFirstSearchResults &other);

    ~BasicDepthFirstSearchResults();

    bool IsReachable(const int &nodeId) const;
    int GetParent(const int &nodeId) const;

    friend class BasicGraph;
};

}


// +-------------------------------------------------------------------------------------------------------------------+
// |  src/graph/base/DirectedGraph.hpp                                                                                 |
// +-------------------------------------------------------------------------------------------------------------------+
namespace graph {

class BasicDirectedGraph : public BasicGraph {
public:
    BasicDirectedGraph();
    explicit BasicDirectedGraph(int numNodes);

    bool IsDirected() const override;

    BasicDirectedGraph &AddEdge(const int &src, const int &dst) override;
};

}


// +-------------------------------------------------------------------------------------------------------------------+
// |  src/graph/base/BasicGraph.cpp                                                                                    |
// +-------------------------------------------------------------------------------------------------------------------+
namespace graph {

BasicGraphEdge::BasicGraphEdge(BasicGraph* graph, BasicGraphNode* src, BasicGraphNode* dst):
        graph(graph), src(src), dst(dst) {
    src->AddOutgoingEdge(this);
    dst->AddIncomingEdge(this);
    if (!this->GetGraph()->IsDirected()) {
        dst->AddOutgoingEdge(this);
        src->AddIncomingEdge(this);
    }
}

BasicGraph* BasicGraphEdge::GetGraph() const {
    return this->graph;
}

BasicGraphNode* BasicGraphEdge::GetSource() const {
    return this->src;
}

BasicGraphNode* BasicGraphEdge::GetDestination() const {
    return this->dst;
}

BasicGraphNode* BasicGraphEdge::GetOpposite(const BasicGraphNode *node) const {
    if (node == this->src) {
        return this->dst;
    }
    if (node == this->dst) {
        return this->src;
    }
    return nullptr;
}


void BasicGraphEdgeArray::Alloc(int capacity) {
    this->capacity = capacity;
    this->edges = (BasicGraphEdge**)realloc(this->edges, this->capacity * sizeof(BasicGraphEdge*));
}

BasicGraphEdgeArray::BasicGraphEdgeArray(): size(0), capacity(4), edges(nullptr) {
    this->Alloc(4);
}

BasicGraphEdge* BasicGraphEdgeArray::operator[](const int &i) const {
    return this->edges[i];
}

int BasicGraphEdgeArray::Size() const {
    return this->size;
}

BasicGraphEdgeArray& BasicGraphEdgeArray::AddEdge(BasicGraphEdge* edge) {
    if (this->size == this->capacity) {
        this->Alloc(this->capacity << 1);
    }
    this->edges[this->size ++] = edge;
    return *this;
}

void BasicGraphEdgeArray::Clear() {
    for (int i = 0; i < this->size; ++ i) {
        this->edges[i] = nullptr;
    }
    this->size = 0;
}

BasicGraphEdge** BasicGraphEdgeArray::begin() const {
    return this->edges;
}

BasicGraphEdge** BasicGraphEdgeArray::end() const {
    return this->edges + this->size;
}


BasicGraphNode::BasicGraphNode(BasicGraph* graph, int id): graph(graph), id(id) {
}

BasicGraphNode& BasicGraphNode::AddIncomingEdge(BasicGraphEdge* edge) {
    this->incoming.AddEdge(edge);
    return *this;
}

BasicGraphNode& BasicGraphNode::AddOutgoingEdge(BasicGraphEdge* edge) {
    this->outgoing.AddEdge(edge);
    return *this;
}

const BasicGraphEdgeArray *BasicGraphNode::GetIncomingEdges() const {
    return &this->incoming;
}

const BasicGraphEdgeArray *BasicGraphNode::GetOutgoingEdges() const {
    return &this->outgoing;
}

int BasicGraphNode::GetId() const {
    return this->id;
}


BasicGraph::BasicGraph(): numNodes(-1), initialized(false), nodes(nullptr) {}

BasicGraph::BasicGraph(int numNodes): numNodes(numNodes), initialized(false), nodes(nullptr) {
    this->Init(numNodes);
}

BasicGraph::~BasicGraph() {
    for (int i = 0; i < this->numNodes; ++ i) {
        delete this->nodes[i];
    }
    delete this->nodes;
    for (int i = 0; i < this->edges.Size(); ++ i) {
        delete this->edges[i];
    }
}

BasicGraph& BasicGraph::Init(int numNodes) {
    if (this->initialized) {
        for (int i = 0; i < this->numNodes; ++ i) {
            delete this->nodes[i];
        }
        delete this->nodes;
        for (int i = 0; i < this->edges.Size(); ++ i) {
            delete this->edges[i];
        }
        this->edges.Clear();
    } else {
        this->initialized = true;
    }
    this->numNodes = numNodes;
    this->nodes = (BasicGraphNode**)malloc(this->numNodes * sizeof(BasicGraphNode*));
    for (int i = 0; i < this->numNodes; ++ i) {
        this->nodes[i] = new BasicGraphNode(this, i);
    }
}

BasicGraphNode* BasicGraph::GetNode(const int &index) const {
    if (index >= this->numNodes || index < 0) {
        throw std::logic_error("Invalid node index.");
    }
    return this->nodes[index];
}

int BasicGraph::Size() const {
    return this->numNodes;
}

std::istream &operator >> (std::istream &in, BasicGraph &g) {
    int numNodes, numEdges;
    in >> numNodes >> numEdges;
    g.Init(numNodes);
    for (int x, y, i = 0; i < numEdges; ++ i) {
        in >> x >> y;
        g.AddEdge(x, y);
    }
    return in;
}

std::ostream &operator << (std::ostream &out, BasicGraph &g) {
    out << g.numNodes << " " << g.edges.Size() << "\n";
    for (int i = 0; i < g.edges.Size(); ++ i) {
        out << g.edges[i]->GetSource()->GetId();
        out << " ";
        out << g.edges[i]->GetDestination()->GetId();
        out << "\n";
    }
    return out;
}

}


// +-------------------------------------------------------------------------------------------------------------------+
// |  src/graph/base/DirectedGraph.cpp                                                                                 |
// +-------------------------------------------------------------------------------------------------------------------+
namespace graph {

BasicDirectedGraph::BasicDirectedGraph() = default;

BasicDirectedGraph::BasicDirectedGraph(int numNodes): BasicGraph(numNodes) {
}

bool BasicDirectedGraph::IsDirected() const {
    return true;
}

BasicDirectedGraph& BasicDirectedGraph::AddEdge(const int &src, const int &dst) {
    this->edges.AddEdge(new BasicGraphEdge(this, this->GetNode(src), this->GetNode(dst)));
}

}


// +-------------------------------------------------------------------------------------------------------------------+
// |  src/graph/base/algorithms/breadth-first-search/BreadthFirstSearch.cpp                                            |
// +-------------------------------------------------------------------------------------------------------------------+
namespace graph {

BasicBreadthFirstSearchResults BasicGraph::BreadthFirstSearch(const int &src) const {
    BasicGraphNode* node = this->GetNode(src);
    BasicBreadthFirstSearchResults results(this);
    results.Run(node);
    return results;
}

BasicBreadthFirstSearchResults BasicGraph::FullBreadthFirstSearch() const {
    BasicBreadthFirstSearchResults results(this);
    for (int i = 0; i < this->numNodes; ++ i) {
        if (!results.IsReachable(i)) {
            results.Run(this->nodes[i]);
        }
    }
    return results;
}

}


// +-------------------------------------------------------------------------------------------------------------------+
// |  src/graph/base/algorithms/depth-first-search/DepthFirstSearch.cpp                                                |
// +-------------------------------------------------------------------------------------------------------------------+
namespace graph {

BasicDepthFirstSearchResults BasicGraph::FullDepthFirstSearch() const {
    BasicDepthFirstSearchResults results(this);
    for (int i = 0; i < this->numNodes; ++ i) {
        if (!results.IsReachable(i)) {
            results.Run(this->nodes[i]);
        }
    }
    return results;
}

BasicDepthFirstSearchResults BasicGraph::DepthFirstSearch(const int &src) const {
    BasicGraphNode* startNode = this->GetNode(src);
    BasicDepthFirstSearchResults results(this);
    results.Run(startNode);
    return results;
}

}


// +-------------------------------------------------------------------------------------------------------------------+
// |  src/graph/base/algorithms/breadth-first-search/BreadthFirstSearchResults.cpp                                     |
// +-------------------------------------------------------------------------------------------------------------------+
namespace graph {

BasicBreadthFirstSearchResults::BasicBreadthFirstSearchResults(const BasicGraph* graph) {
    this->graph = graph;
    this->distances = new int[this->graph->Size()];
    this->parents = new int[this->graph->Size()];
    this->roots = new int[this->graph->Size()];
    for (int i = 0; i < this->graph->Size(); ++ i) {
        this->distances[i] = -1;
        this->parents[i] = -1;
        this->roots[i] = -1;
    }
}

BasicBreadthFirstSearchResults::BasicBreadthFirstSearchResults(const BasicBreadthFirstSearchResults &other) {
    this->graph = other.graph;
    this->distances = new int[this->graph->Size()];
    this->parents = new int[this->graph->Size()];
    this->roots = new int[this->graph->Size()];
    for (int i = 0; i < this->graph->Size(); ++ i) {
        this->distances[i] = other.distances[i];
        this->parents[i] = other.parents[i];
        this->roots[i] = other.roots[i];
    }
}

BasicBreadthFirstSearchResults::~BasicBreadthFirstSearchResults() {
    delete[] this->parents;
    delete[] this->distances;
    delete[] this->roots;
}

void BasicBreadthFirstSearchResults::Extend(const BasicGraphNode *node, const BasicGraphNode *parent,
                                            const BasicGraphEdge *edge) {
    if (!parent) {
        this->parents[node->GetId()] = -1;
        this->distances[node->GetId()] = 0;
        this->roots[node->GetId()] = node->GetId();
    } else {
        this->parents[node->GetId()] = parent->GetId();
        this->distances[node->GetId()] = this->distances[parent->GetId()] + 1;
        this->roots[node->GetId()] = this->roots[parent->GetId()];
    }
}

void BasicBreadthFirstSearchResults::Run(const BasicGraphNode *node) {
    this->Extend(node);
    auto queue = (const BasicGraphNode**)malloc(this->graph->Size() * sizeof(const BasicGraphNode*));
    int first = 0, last = 0;
    queue[last ++] = node;
    while (first < last) {
        node = queue[first ++];
        for (BasicGraphEdge* edge: *node->GetOutgoingEdges()) {
            const BasicGraphNode* other = edge->GetOpposite(node);
            if (!this->IsReachable(other->GetId())) {
                this->Extend(other, node, edge);
                queue[last ++] = other;
            }
        }
    }
    free(queue);
}

int BasicBreadthFirstSearchResults::GetParent(const int &nodeId) const {
    return this->parents[nodeId];
}

int BasicBreadthFirstSearchResults::GetDistance(const int &nodeId) const {
    return this->distances[nodeId];
}

int BasicBreadthFirstSearchResults::GetRoot(const int &nodeId) const {
    return this->roots[nodeId];
}

bool BasicBreadthFirstSearchResults::IsReachable(const int &nodeId) const {
    return this->GetRoot(nodeId) > -1;
}

}


// +-------------------------------------------------------------------------------------------------------------------+
// |  src/graph/base/algorithms/depth-first-search/DepthFirstSearchResults.cpp                                         |
// +-------------------------------------------------------------------------------------------------------------------+
namespace graph {

BasicDepthFirstSearchResults::BasicDepthFirstSearchResults(const BasicGraph *graph) {
    this->graph = graph;
    this->parents = new int[this->graph->Size()];
    this->roots = new int[this->graph->Size()];
    for (int i = 0; i < this->graph->Size(); ++ i) {
        this->parents[i] = -1;
        this->roots[i] = -1;
    }
}

BasicDepthFirstSearchResults::BasicDepthFirstSearchResults(const BasicDepthFirstSearchResults &other) {
    this->graph = other.graph;
    this->parents = new int[this->graph->Size()];
    this->roots = new int[this->graph->Size()];
    for (int i = 0; i < this->graph->Size(); ++ i) {
        this->parents[i] = other.parents[i];
        this->roots[i] = other.roots[i];
    }
}

BasicDepthFirstSearchResults::~BasicDepthFirstSearchResults() {
    delete[] this->parents;
    delete[] this->roots;
}

int BasicDepthFirstSearchResults::GetParent(const int &nodeId) const {
    return this->parents[nodeId];
}

bool BasicDepthFirstSearchResults::IsReachable(const int &nodeId) const {
    return this->roots[nodeId] != -1;
}

void BasicDepthFirstSearchResults::Extend(const BasicGraphNode *node, const BasicGraphNode *parent,
                                          const BasicGraphEdge *edge) {
    if (parent) {
        this->parents[node->GetId()] = parent->GetId();
        this->roots[node->GetId()] = this->roots[parent->GetId()];
    } else {
        this->roots[node->GetId()] = node->GetId();
    }
}

void BasicDepthFirstSearchResults::Run(const BasicGraphNode *node, const BasicGraphNode *parent,
                                       const BasicGraphEdge *edgeToParent) {
    this->Extend(node, parent, edgeToParent);
    for (BasicGraphEdge* edge : *node->GetOutgoingEdges()) {
        BasicGraphNode* other = edge->GetOpposite(node);
        if (!this->IsReachable(other->GetId())) {
            this->Run(other, node, edge);
        }
    }
}

}


// +-------------------------------------------------------------------------------------------------------------------+
// |  examples/BFS.cpp                                                                                                 |
// +-------------------------------------------------------------------------------------------------------------------+
using namespace std;
using namespace graph;

int main() {
    freopen("bfs.in", "r", stdin);
    freopen("bfs.out", "w", stdout);

    int n, m, s;
    cin >> n >> m >> s;
    BasicDirectedGraph g(n);
    for (int i = 1, x, y; i <= m; ++ i) {
        cin >> x >> y;
        g.AddEdge(x - 1, y - 1);
    }
    BasicBreadthFirstSearchResults results = g.BreadthFirstSearch(s - 1);
    for (int i = 0; i < n; ++ i) {
        cout << results.GetDistance(i) << (i + 1 == n ? "\n" : " ");
    }
    return 0;
}