#include <bits/stdc++.h>
#include <vector>
#include <queue>
using namespace std;
ifstream f("bfs.in");
ofstream g("bfs.out");

void memorareLiAd(vector<vector<int>> &liAd, int nrNoduri, int nrMuchii, bool orientat)
{
  for(int i=0; i<nrMuchii; i++)
  {
    int x, y;
    f>>x>>y;
    liAd[x].push_back(y);
    if(!orientat)
      liAd[y].push_back(x);
  }
}

void drumMinim(vector<vector<int>> liAd, int nodStart, int nrNoduri)
{
  vector<int> dist(nrNoduri+1, -1); // vector de distante de la nodul de start la celelalte noduri
  queue<int> q; // coada de noduri de vizitat
  q.push(nodStart); // adaugam nodul de start in coada
  dist[nodStart] = 0; // distanta de la nodul de start la el insusi este 0
  while(!q.empty()) // cat timp mai avem noduri de vizitat
  {
    int nodCurent = q.front(); // nodul curent este primul nod din coada
    q.pop(); // scoatem nodul curent din coada
    for(int i=0; i<liAd[nodCurent].size(); i++) // pentru fiecare vecin al nodului curent
    {
      int vecin = liAd[nodCurent][i];
      if(dist[vecin] == -1) // daca nu am mai vizitat nodul vecin
      {
        dist[vecin] = dist[nodCurent] + 1; // distanta de la nodul de start la nodul vecin este distanta de la nodul de start la nodul curent + 1
        q.push(vecin); // adaugam nodul vecin in coada pentru a-l vizita, ca sa mergem la vecinii sai si tot asa...
      }
    }
  }
  for(int i=1; i<=nrNoduri; i++)
    g<<dist[i]<<" ";
}

int main()
{
  int N,M,S;
  f>>N>>M>>S;
  vector<vector<int>> liAd(N+1);
  memorareLiAd(liAd, N, M, 1);
  drumMinim(liAd, S, N);
  f.close(); g.close();
  return 0;
}