#include <algorithm>
#include <iostream>
using namespace std;
int n,m,s,v[2][100],a[100][100],i,j,st,dr,uz[100],coada[100],dist[100],start;
int main()
{
	freopen ("bfs.in", "r", stdin);
	freopen("bfs.out","w", stdout);
	cin>>n;
	cin>>m;
	cin>>s;
	for(i=1;i<=m;i++)
		{
			int x,y;
			cin>>x>>y;
			a[x][y]=1;
		}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			cout<<a[i][j]<<" ";
		cout<<endl;
	}
	for(i=1;i<=m;i++)
		dist[i]=-1;
	coada[1] = s;
	uz[s] = 1;
	st = dr = 1;
	dist[s ] = 0;
	while ( st<=dr)
		{
		for ( i = 1; i <=n ; i ++ )
			if ( a[ coada[st] ] [i] && !uz[i] )
			{
			dist[i] = dist[ coada[st] ] + 1;
			dr++;
			coada[dr] = i;
			uz[i] = 1;
			}
		st++;
	}	
	for ( i = 1; i<=n; i++)
		cout<<dist[i]<<" ";
		//for(j=1;j<=n;j++)
		//	cout<<v[i][j]<<" ";
		//cout<<endl;
	return 0;
}