// dfs: depth first search
// cautare in adancime

// x = nod de start
// y = nod cautat din y
// x = 1, y = 5
// reprezentare lista de adiacenta
// 1: 2,3
// 2; 1,4,5
// 3: 1,4
// 4: 2
// 6:
// inseram elem 1 in stiva si apoi cautam un nod neparcurs
// st: 1 si stergem 1  apoi punem 2, apoi stergem 2 punem 4
// viz[i] = nod inserat in stiva(def: false)
// viz[1] = true
// viz[2] = true

// #include <iostream>
// #include <string>
// #include <vector>
// using namespace std;
// i
//
// st = []
// st.append(start)
// vector<int>adj();
// while (st.size()>0) {
//     int nod = st.top(); st.pop();
//     viz[nod] = 1;
//     for (int vecin:adj[nod]) {
//         if (!viz[vecin]) {
//             st.append(vecin)
//             viz[vecin] = true;
//         }
//     }
// }
///DFS VARIANTA MEA
// #include <iostream>
// #include <vector>
// #include <stack>
// using namespace std;
// int main() {
//     int n =6, m = 6;
//     stack <int> st;
//     vector<vector<int>> adj(n+1);
//     vector<int> viz(n+1,0);
//     int s, d,x,y;
//     cin>>s>>d;
//     for (int i = 1; i <= m; i++ ) {
//         cout<< "muchia " << i;
//         cin >> x >> y;
//         adj[x].push_back(y);
//         adj[y].push_back(x);
//     }
//     //prima data pun nodul de start pe stack
//     st.push(s);
//     viz[s] = 1;
//     //alg continua cat timp stiva nu e goala
//     while (!st.empty()) {
//         int current = st.top();
//         cout << current << " ";
//         if (current == d) {
//             cout << "\nam gasit nodul end\n";
//             break;
//         }
//         st.pop();
//         for (auto vecin: adj[current]) {
//             if (!viz[vecin]) {
//                 st.push(vecin);
//                 viz[vecin] = 1;
//             }
//         }
//     }
// }
/// DFS varianta MEA recursiva
// #include <iostream>
// #include <vector>
// using namespace std;
// int n =6, m = 6;
// vector<vector<int>> adj(n+1);
// vector<int> viz(n+1,0);
// int s, d,x,y;
// bool found = false;
// void dfs(int nod) {
//     if (found) return;
//     cout << nod << endl;
//     if (nod == d) {
//         found = true;
//         cout << "am gasit nodul end \n";
//         return;
//     }
//     for (auto vecin: adj[nod]) {
//         if (viz[vecin] == 0) {
//             viz[vecin] = 1;
//             dfs(vecin);
//         }
//     }
// }
// int main() {
//
//     cin>>s>>d;
//     for (int i = 1; i <= m; i++ ) {
//         cout<< "muchia " << i;
//         cin >> x >> y;
//         adj[x].push_back(y);
//         adj[y].push_back(x);
//     }
//     viz[s] = 1;
//     dfs(s);
// }

// dfs: varianta recursiva complexitate timp O(n+m) si spatiu la fel care nu cauta nodul end
// void dfs(int nod) {
//     cout << nod << " ";
//     viz[nod] = true;
//     for ( int vecin: adj[nod]) {
//         if (!viz[vecin]) {
//             //viz[vecin] = 1;
//             dfs(vecin);
//         }
//     }
// }

///memorarea unui graf
///scrieti cun subprogram pentru construirea in memorie a matricei de adiacenta
///a unui graf citit din graf.in si un subprogram pt afisare
// #include <iostream>
// #include <fstream>
// #include <vector>
// using namespace std;
// ifstream fin("graf.in");
// int x, y, n,m;
// vector<vector <int>> Mat;
// void construire() {
//     fin >> n >> m;
//     Mat.assign(n+1, vector <int> (n+1));
//     for(int i=0;i<m;i++) {
//         fin >> x >> y;
//         Mat[x][y] = 1;
//         Mat[y][x] = 1;
//     }
//     fin.close();
// }
//
// void afisare() {
//     for(int i=1;i<=n;i++) {
//         for(int j=1;j<=n;j++) {
//             cout << Mat[i][j] << " ";
//         }
//         cout << endl;
//     }
// }
// int main() {
//     construire();
//     afisare();
//     return 0;
// }

// BFS: breadth first search
// cautare in latime
// x-> y
// 1, dupa il taiem si punem, 2 si 3, vizitam pe 1, apoi vizitam pe 2 si 3
// cea mai scurta distanta dintre doua noduri
// algoritmul lui Lee
//
// queue < int> q;
// q.push(x);
// viz[x] = true;
// while (q.size()>0)
// {
//     int nod = q.front();
//     cout << nod << " ";
//     q.pop();
//     for (int vecin: adj[nod]) {
//         if (!viz[vecin]) {
//             viz[nod] = true;
//             q.push(nod);
//         }
//     }
// }

///BFS VARIANTA MEA
// #include <iostream>
// #include <fstream>
// #include <queue>
// #include <vector>
// using namespace std;
// ifstream fin("bfs.in");
// ofstream fout("bfs.out");
// int main() {
//     int m,n,x,y,s,d;
//     cin>>n>>m;
//     cin>>s>>d;
//     vector<vector<int>> adj(n+1);
//     queue<int> q;
//     vector viz(n+1, 0);
//     for (int i = 0; i < m ;i++) {
//         cin >>x>>y;
//         adj[x].push_back(y);
//         adj[y].push_back(x);
//     }
//     q.push(s);
//     viz[s] = 1;
//     while(!q.empty()) {
//         auto current = q.front();
//         q.pop();
//         cout<<current << " ";
//         if(current == d) {
//             cout<<"\n am gasit nodul end \n";
//             break;
//         }
//         for (auto vecin : adj[current]) {
//             if (viz[vecin] == 0) {
//                 q.push(vecin);
//                 viz[vecin] = 1;
//             }
//         }
//     }
// }

/// INFOAREANA BFS
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int main() {
    int m,n,x,y,s,d;
    fin>>n>>m>>s;
    vector<vector<int>> adj(n+1);
    queue<pair<int,int>> q;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> rez;

    vector<int> viz(n+1, 0);
    for (int i = 0; i < m ;i++) {
        fin >>x>>y;
        adj[x].push_back(y);
    }
    q.push(make_pair(s,0));
    rez.push(make_pair(s,0));
    viz[s] = 1;
    while (!q.empty()) {
        int current = q.front().first;
        int dist = q.front().second;
        q.pop();
        for (auto vecin: adj[current]) {
            if (viz[vecin] == 0) {
                viz[vecin] = 1;
                q.push(make_pair(vecin, dist+1));
                rez.push(make_pair(vecin, dist+1));
            }
        }
    }
    for (int i = 1; i<= n ; i++) {
        if (viz[i] == 0) {
            rez.push(make_pair(i,-1));
        }
    }
    while (!rez.empty()) {
        fout<<rez.top().second<<" ";
        rez.pop();
    }
}


// Problema: Se dau doua noduri x,y din graful G
// Sa se determine distanta cea mai scurta dintre x si y

// din 1 in 5,
// dist: 3 cu dfs

// dist[N] = {0};
//
// queue<int> q;
// q.push(x);
// viz[x] = true;
// dist[y] = 0;
// while(q.size() > 0) {
//     int nod = q.front();
//     q.pop();
//     for ( int vecin: adj[nod]) {
//         viz[vecin] = true;
//         dist[vecin] = min(dist[vecin], dist[nod]+1);//pt  bfs nu e nevoie de atsa , pt dfs da
//
//     }
// }
//O(n+m)