#include<fstream>
#include<vector>
#include<queue>
using namespace std;

vector<int> a[100010];
queue<int> Q;
int n,m,s, viz[100010], d[100010];

ifstream f("bfs.in");
ofstream g("bfs.out");

int main()
{
    f>>n>>m>>s;
    for(int  i = 1; i<=n; ++i)
        d[i] = -1;
    for(int i = 1; i<=m; ++i)
    {
        int x,y;
        f>>x>>y;
        a[x].push_back(y);
    }

     Q.push(s);
     viz[s] = 1;
     d[s] = 0;

     while(!Q.empty())
     {
         int u = Q.front();
         Q.pop();

         for(int j =0; j<a[u].size(); ++j)
         {
             int vec = a[u][j];
             if(!viz[vec])
             {
                Q.push(vec);
                viz[vec] = 1;
                d[vec] = d[u] + 1;
             }
         }
     }

    for(int i =1; i<=n; ++i)
        g<<d[i]<<" ";
    g<<"\n";

    return 0;
}