#include <iostream>
using namespace std;
#include <list>
#include <queue>
#include <fstream>

class Graph{

int V;

list<int>*adj;

public:
    Graph(int v)
    {
        this->V=v;
        adj=new list<int>[v+1];
    }

    void addedge(int m,int n)
    {
        adj[m].push_back(n);
    }

    vector<int> BFS(int s)
    {

        vector<int>distante(V+1,-1);
        distante[s]=0;
        bool* vizitat=new bool[V];

        for(int i=1;i<=V;i++)
            vizitat[i]=false;

        queue<int> q;

        vizitat[s]=true;
        q.push(s);
        list<int>::iterator i;
        int sursa;
        while(!q.empty())
        {
            sursa=q.front();
            //cout<<s<<" ";
            q.pop();
            for(i=adj[sursa].begin();i!=adj[sursa].end();++i)
            {
                if(!vizitat[*i])
                {
                    vizitat[*i]=true;
                    distante[*i]=distante[sursa]+1;
                    q.push(*i);
                }
            }
        }
       return distante;
    }
};



int main()
{


int n,m,s;
ifstream f("bfs.in");
ofstream g("bfs.out");

f>>n>>m>>s;

Graph x(n);

for(int i=0;i<m;i++)
{
    int a,b;
    f>>a>>b;
    x.addedge(a,b);
}

vector<int> u=x.BFS(s);
for(int i=1;i<=n;i++)
    g<<u[i]<<" ";




    return 0;
}