#include <bits/stdc++.h>
#define asd 20000000

using namespace std;

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

int a, b, m, n, s;

char viz[100001];

int main()
{
	in >> n >> m >> s;
	vector < int > v[n+1];
	for(int i = 0; i < m; i++)
	{
		in >> a >> b;
	    v[a].push_back(b);
	}
	
/*	for (int i = 1; i <= n; i++) {
		cout << i << " -> ";
		for (int j = 0; j < v[i].size(); j++) {
			cout << v[i][j] << ", ";
		}
			cout << "\n";
	}
*/	
	queue < int > q;
	int prnt[n+1];
	int dist[n+1];
	
	for(int i = 1; i <= n; i++) dist[i] = asd;
	
	dist[s] = 0;
	
	cout << dist[1] << '\n';
	
	q.push(s);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for(int i = 0; i < v[x].size(); i++) 
		{
			if(dist[v[x][i]] > dist[x] + 1 || dist[v[x][i]] == asd) 
			{ 
				q.push(v[x][i]);
				dist[v[x][i]] = dist[x] + 1;
			}
		}
	}
	
	for(int i = 1; i <= n; i++) 
	{
		if(dist[i] == asd) out << -1 << " ";
		else out << dist[i] << " ";
	}
	
	return 0;
}