#include <stdlib.h>
#include <fstream>
#include <vector>
using namespace std;

#define maxn 100010

vector<int>a[maxn];

int g[maxn],s[maxn],cost[maxn];
int n,m,st,l;

void bfs(int nod){
     int i,j;
     memset(cost, - 1, sizeof(cost));
     
     l = 1;
     cost[nod] = 0;
     s[l] = nod;
     
     for (i = 1; i <= l; i++)
         for (j = 0; j < g[s[i]]; j++)
         if (cost[a[s[i]][j]] == -1)
         {
            s[++l] = a[s[i]][j];
            cost[s[l]] = cost[s[i]] + 1;
            }

}

int main(){
    int i,x,y;
    ifstream fin;
	ofstream fout;
	fin.open("bfs.in");
	fout.open("bfs.out");
    
    fin >> n >> m >> st;
    
    for (i = 1; i <= m; i++){
		fin >> x >> y;
        a[x].push_back(y);
    }
    for (i = 1; i <= n; i++)
		g[i] = a[i].size();
    
    bfs(st);
    
    for (i = 1; i <= n; i++)
		fout << cost[i];
	    fout << endl;

	return 0;
}