#include <queue>
#include <fstream>
#include <iostream>
#include <cstdlib>

using namespace std;

ifstream fin ("bfs.in");
ofstream fout ("bfs.out");

vector <int> L[1000009];

int n,m,viz[100009],S;
int niv[100009];

void Citire()
{
	int x,y,i;
	fin >> n; // numarul de noduri
	fin >> m; // nr de muchii
	fin >> S; // nod de plecare
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y;
		L[x].push_back(y);
    }
}

void BFS(int k)
{      /// coada dinamica -> STL, la final ramane vida
	int i, j; 
	queue<int> q;
	q.push(k);
	viz[k] = 1;
	niv[k] = 0;
	while (!q.empty())
	{
		k = q.front();
		q.pop();
		cout << k << " ";
		for (j=0; j< L[k].size(); j++)
           {  i=L[k][j];
              if (!viz[i]) 
              {  q.push(i); 
			     niv[i] = niv[k] + 1;
                 viz[i]=1;
              }
		}
    }
}
 
void Afisare()
{
	int i; 
	for (i=1; i<=n; i++)
	if (niv[i]==0 && i!=S) fout<<"-1 ";
	else fout<<niv[i]<<" ";
	
	fout<<"\n";
}

int main ()
{
	int i;
    Citire();
    BFS(S);
    Afisare();
    fin.close();
    fout.close();
    return 0;
}