#include <bits/stdc++.h>

class Graph
{
public:
        Graph(const std::size_t nr_noduri, std::vector<std::vector<int>>&& l_adiacenta)
            : nr_noduri(nr_noduri)
            , l_adiacenta(std::move(l_adiacenta))
        {
        }

        int componente_conexe() const;

        std::vector<int> distante_minime(const int start) const;

        std::vector<int> sortare_topologica() const;

        std::vector<int> grade_interne() const;

        static bool hakimi(std::vector<int>);

private:
        void DFS(std::vector<bool>& visited, int src) const;

        void DFS_ordine(std::vector<unsigned char>& visited, std::vector<int>& res,
                        const int src) const;

        void BFS(std::vector<int>& dists, int start) const;

private:
        std::size_t nr_noduri;
        std::vector<std::vector<int>> l_adiacenta;
};

int Graph::componente_conexe() const
{
        std::vector<bool> visited(nr_noduri + 1, false);

        int res = 0;
        for(int node = 1; node <= (int)nr_noduri; ++node)
        {
                if(!visited[node])
                {
                        ++res;
                        DFS(visited, node);
                }
        }

        return res;
}

std::vector<int> Graph::distante_minime(const int start) const
{
        std::vector<int> distante(nr_noduri + 1, -1);

        BFS(distante, start);

        return distante;
}

std::vector<int> Graph::sortare_topologica() const
{
        std::vector<int> sorted;

        const auto grd_i = grade_interne();
        std::vector<unsigned char> viz(nr_noduri + 1, false);

        for(std::size_t node = 1; node <= nr_noduri; ++node)
        {
                if(grd_i[node] == 0 && !viz[node])
                {
                        DFS_ordine(viz, sorted, node);
                }
        }

        std::reverse(sorted.begin(), sorted.end());

        return sorted;
}

std::vector<int> Graph::grade_interne() const
{
        std::vector<int> res(nr_noduri + 1, 0);

        for(auto& l : l_adiacenta)
        {
                for(int v : l)
                {
                        ++res[v];
                }
        }

        return res;
}

void Graph::DFS(std::vector<bool>& visited, int start) const
{
        visited[start] = true;

        for(int v : l_adiacenta[start])
        {
                if(!visited[v])
                {
                        DFS(visited, v);
                }
        }
}

void Graph::DFS_ordine(std::vector<unsigned char>& visited, std::vector<int>& res,
                       const int src) const
{
        visited[src] = true;

        for(int v : l_adiacenta[src])
        {
                if(!visited[v])
                {
                        DFS_ordine(visited, res, v);
                }
        }

        res.push_back(src);
}

void Graph::BFS(std::vector<int>& dists, int start) const
{
        std::queue<int> q;
        q.push(start);
        dists[start] = 0;

        while(!q.empty())
        {
                const auto node = q.front();
                q.pop();

                for(int v : l_adiacenta[node])
                {
                        if(dists[v] == -1)
                        {
                                q.push(v);
                                dists[v] = dists[node] + 1;
                        }
                }
        }
}

bool Graph::hakimi(std::vector<int> degrees)
{
        if(degrees.empty())
        {
                return true;
        }

        if(std::any_of(degrees.begin(), degrees.end(),
                       [](const int deg)
                       {
                               return deg < 0;
                       }))
        {
                return false;
        }

        while(true)
        {
                std::sort(degrees.begin(), degrees.end());
                if(degrees.back() == 0)
                {
                        return true;
                }

                const int current_deg = degrees.back();
                degrees.pop_back();

                if(static_cast<std::size_t>(current_deg) > degrees.size())
                {
                        return false;
                }

                for(auto it = degrees.rbegin(); it != degrees.rbegin() + current_deg; ++it)
                {
                        --(*it);
                }

                if(std::any_of(degrees.begin(), degrees.end(),
                               [](const int deg)
                               {
                                       return deg < 0;
                               }))
                {
                        return false;
                }
        }
}

int main()
{
        int n, m, s;
        std::scanf("%d %d %d", &n, &m, &s);

        const Graph g = [&]()
        {
                std::vector<std::vector<int>> list(n + 1);
                for(int i = 0; i < m; ++i)
                {
                        int x, y;
                        std::scanf("%d %d", &x, &y);

                        list[x].push_back(y);
                }

                return Graph(n, std::move(list));
        }();

        const auto dists = g.distante_minime(s);
        for(std::size_t i = 1; i < dists.size(); ++i)
        {
                std::printf("%d ", dists[i]);
        }

        puts("");
}

static const int x = []()
{
        std::freopen("bfs.in", "r", stdin);
        std::freopen("bfs.out", "w", stdout);
        return 0;
}();