#include <fstream>
#include <queue>
using namespace std;
ifstream d("bfs.in");
ofstream o("bfs.out");
int g[10005][10005],c[100005],i,j,x,y,n,m,s,k;
queue<int> q;
int main()
  {
    d>>n>>m>>s;
    for (i=1;i<=m;i++) {d>>x>>y; g[x][y]=1;};
    q.push(s); c[s]=1;
    while (!q.empty())
      {
        k=q.front();
        for (i=1;i<=n;i++)
          if ((g[k][i]==1)&(c[i]==0))
            {
              c[i]=c[k]+1;
              q.push(i);
            }
        q.pop();
      }
    for (i=1;i<=n;i++) o<<c[i]-1<<' ';
  }