#include<fstream>
#include<vector>
#include<deque>
#include<list>
#include<algorithm>

using namespace std;

ifstream in("bfs.in");

ofstream out("bfs.out");

const int N=100001;

vector <int> a[N];

vector <int> z(N,-1);

int n,s;

void cit()
{
	int x,y,m;
	in>>n>>m>>s;
	while(m--)
	{
		in>>x>>y;
		a[x].push_back(y);
	}
}

void befese()
{
	int x;
	deque <int> c;
	c.push_back(s);
	z[s]=0;
	while (!c.empty())
	{
		x=c.front();
		c.pop_front();
		for( vector<int>::iterator it=a[x].begin() ; it!=a[x].end() ; ++it )
		//for( int *it=&a[x].front() ; it!=&a[x].back() ; ++it )
			if(z[*it]==-1)
			{
				c.push_back(*it);
				z[*it]=1+z[x];
			}
	}
	for( int it=1 ; it<=n ; ++it )
		out<<z[it];
}

int main()
{
	cit();
	befese();
	return 0;
}