#include <bits/stdc++.h>
#define asd 20000000
using namespace std;
ifstream in("bfs.in");
ofstream out("bfs.out");
int a, b, m, n, s;
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);
	}
	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;
}