/* LAB 1A - MEMORAREA UNUI GRAF
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("graf.in");
struct Node{
    int val;
    Node* next;
};
int n,m;//n = nr noduri, m = nr muchii
vector<vector<bool>> ad;
vector<Node*> root;
vector<Node*> current;
void init_mat_ad(bool orientat)
{
    for(int i=0;i<m;i++)
    {
        int x,y;
        fin>>x>>y;
        ad[x][y] = 1;
        if(orientat == false)
            ad[y][x] = 1;
    }
}
void afis_mat_ad()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cout<<ad[i][j]<<' ';
        cout<<'\n';
    }
}
void init_list_ad(bool orientat)
{
    for(int i=0;i<m;i++)
    {
        int x,y;
        fin>>x>>y;
        if(root[x] == nullptr)
        {
            root[x] = new Node{y,nullptr};
            current[x] = root[x];
        }
        else{
            Node* temp = new Node{y,nullptr};
            current[x]->next = temp;
            current[x] = temp;
        }
        if(orientat == false)
        {
            if(root[y] == nullptr)
            {
                root[y] = new Node{x,nullptr};
                current[y] = root[y];
            }
            else{
                Node* temp = new Node{x,nullptr};
                current[y]->next = temp;
                current[y] = temp;
            }
        }
    }
}
void afis_list_ad()
{
    for(int i=1;i<=n;i++)
    {
        Node* temp = root[i];
        cout<<"Vecinii nodului "<<i<<": ";
        while(temp!=nullptr)
        {
            cout<<temp->val<<' ';
            temp = temp->next;
        }
        cout<<'\n';
    }
}
void convert_list_to_mat()
{
    for(int i=1;i<=n;i++)
    {
        Node* temp = root[i];
        while(temp!=nullptr)
        {
            ad[i][temp->val] = 1;
            temp = temp->next;
        }
    }
}
void convert_mat_to_list()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(ad[i][j] == 1)
            {
                if(root[i] == nullptr)
                {
                    root[i] = new Node{j,nullptr};
                    current[i] = root[i];
                }
                else{
                    Node* temp = new Node{j,nullptr};
                    current[i]->next = temp;
                    current[i] = temp;
                }
            }
}
int main()
{
    fin>>n>>m;
    ad.resize(n+1);
    root.resize(n+1);
    current.resize(n+1);
    for(int i=1;i<=n;i++)
        ad[i].resize(n+1);
    for(int i=1;i<=n;i++)
        root[i] = nullptr;
    init_list_ad(false);
    afis_list_ad();
    return 0;
}
*/
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("bfs.in");
ofstream cout("bfs.out");
int main()
{
    int n,m,s;
    vector<int> viz;
    vector<vector<int>> arce;
    vector<int> distante;
    queue<int> q;
    cin>>n>>m>>s;
    viz.resize(n+1,0);
    arce.resize(n+1);
    distante.resize(n+1);
    distante[s] = 0;
    q.push(s);
    viz[s] = 1;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        arce[x].push_back(y);
    }
    while(!q.empty())
    {
        int tp = q.front();
        for(int elem:arce[tp])
            if(!viz[elem])
            {
                q.push(elem);
                distante[elem] = distante[tp] + 1;
                viz[elem] = 1;
            }
        q.pop();
    }
    for(int i = 1;i<=n;i++)
        if(viz[i] == 0)
            distante[i] = -1;
    for(int i=1;i<=n;i++)
        cout<<distante[i]<<' ';
    return 0;
}