#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
//#include "Graph.h"
//#include "DirectedGraph.h"
//#include "UndirectedGraph.h"
using namespace std;


class Graph {
    int nrNodes; //number of nodes
    vector<vector<int>> edges; // list of connections between nodes
public:
    Graph(int _nrNodes);
    int getNrNodes() const;
    void setEdge(int node, int neighbour);
    int nrConnectedComponents();
    void printEdges();
    vector<int> minDistanceBFS(int start);
    ~Graph();
private:
    void DFS(int, vector<int>&);
};

Graph::Graph(int _nrNodes)
{
    this -> nrNodes = _nrNodes;
    this -> edges.resize(this -> nrNodes + 1, vector<int>());
    /*
     * Nodes start from 1, but index starts at 0
     */
}

int Graph::getNrNodes() const
{
    return this -> nrNodes;
}

int Graph::nrConnectedComponents()
{
    int ans = 0;
    vector<int>visited(this -> nrNodes+1, 0);
    for(int i = 1 ; i <= this -> nrNodes; ++i)
        if(visited[i] == 0)
        {
            DFS(i, visited);
            ++ans;
        }
    return ans;
}
void Graph::DFS(int start, vector<int>& visited)
{
    visited[start] = 1;
    for(int i = 0; i < edges[start].size(); ++i)
    {
        int neighbour = edges[start][i];
        if(visited[neighbour] == 0)
        {
            visited[neighbour] = 1;
            DFS(neighbour, visited);
        }
    }
}

vector<int> Graph::minDistanceBFS(int start)
{
    vector<int>distances(this->nrNodes + 1, -1);
    distances[start] = 0;

    queue<int>toBeVisited;
    toBeVisited.push(start);

    int dist = 1;
    bool ok = false;

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

        for(auto it: this->edges[x])
        {
            if(distances[it] == -1)
            {
                ok = true;       // if a node has no neighbours, dist should not be increased
                distances[it] = dist;
                toBeVisited.push(it);
            }
        }

        if(ok)
        {
            ok = false;
            dist++;
        }

    }     //while loop ended

    return distances;
}

Graph::~Graph()
{
    this -> nrNodes = 0;
    for(int i = 1; i <= edges.size(); ++i)
        this -> edges[i].clear();
}

void Graph::printEdges()
{
  for(int i = 1; i < edges.size(); i++)
  {
      cout << i<< ": ";
      for(auto it: edges[i])
          cout << it<< " ";
      cout << "\n";
  }
}

void Graph::setEdge(int node, int neighbour)
{
   this ->edges[node].push_back(neighbour);
}


//------------------------------------------------------------------------------------------

class UndirectedGraph: public Graph{

public:
    UndirectedGraph(int _nrNodes);
    void addEdge(int node, int neighbour);
    ~UndirectedGraph();
};


UndirectedGraph::UndirectedGraph(int _nrNodes): Graph(_nrNodes){}

void UndirectedGraph::addEdge(int node, int neighbour)
{
    this -> setEdge(node, neighbour);
    this -> setEdge(neighbour, node);
}

UndirectedGraph::~UndirectedGraph() {}
//----------------------------------------------------------------------------------------------------

class DirectedGraph: public Graph {

public:
    DirectedGraph(int _nrNodes);
    void addEdge(int node, int neighbour);
   ~DirectedGraph();
};


DirectedGraph::DirectedGraph(int _nrNodes): Graph(_nrNodes) {}

void DirectedGraph::addEdge(int node, int neighbour)
{
    this -> setEdge(node, neighbour);
}

DirectedGraph::~DirectedGraph() {}

//---------------------------------------------------------------------------
int main()
{
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");

    int n, m, x, y, s;
    cin >> n >> m >> s;

    DirectedGraph *dg = new DirectedGraph(n);
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        dg -> addEdge(x, y);
    }

    vector<int>d = dg-> minDistanceBFS(s);

    for(unsigned int i = 1; i < d.size(); ++i)
        cout << d[i]<< " ";

    return 0;

}