#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <fstream>
void BFS(const std::vector<std::vector<int>>& adj, std::vector<int>& distances, int source)
{
std::queue<int> q;
q.push(source);
while(!q.empty())
{
auto u = q.front();
q.pop();
for(auto v : adj[u - 1])
{
if(distances[v - 1] == -1)
{
q.push(v);
distances[v - 1] = distances[u - 1] + 1;
}
}
}
}
int main()
{
std::ifstream in("bfs.in");
std::ofstream out("bfs.out");
int N, M, S;
in >> N >> M >> S;
std::vector<std::vector<int>> adj(N);
std::vector<int> distances(N, -1);
distances[S - 1] = 0;
int u, v;
for(int i = 0; i < M; i++)
{
in >> u >> v;
adj[u - 1].push_back(v);
}
BFS(adj, distances, S);
for(auto d : distances)
{
out << d << " ";
}
out << "\n";
return 0;
}