#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream fin("bfs.in");
ofstream fout("bfs.out");


class Graph{

protected:
    int n, m; /// n -> nr noduri / m -> nr muchii
public:
    vector<vector<int> > l; /// lista de adiacenta
    //vector<vector<int> > a; /// matricea de adiacenta?

public:
    Graph(int n = 1, int m = 0);
    Graph(const Graph &g);
    Graph& operator= (const Graph &g);

    void set_numEdges(int m);
    int get_numEdges();
    int get_numNodes();

    virtual ostream& print(ostream& out) const;
    virtual istream& read(istream& in);

    friend istream& operator>>(istream& in, Graph& obj);
    friend ostream& operator<<(ostream& out, const Graph& obj);

    virtual ~Graph() = 0;
    void dfs(int start);
    void do_dfs(int start, vector<bool> &viz, bool print);
    int num_of_components();
    void bfs(int start, vector<int> &dist);
    void dist_from_node(int start);




};

/// constructori
Graph :: Graph (int n, int m) : l(n){
    this->n = n;
    this->m = m;
}

Graph :: Graph (const Graph &g) : l(g.n) {
    this->n = g.n;
    this->m = g.m;
}


/// setteri
void Graph :: set_numEdges(int m) {
    this->m = m;
}


/// getteri
int Graph :: get_numEdges() {
    return m;
}

int Graph :: get_numNodes() {
    return n;
}


/// operatori
Graph& Graph :: operator= (const Graph &g){
     if(this != &g){
            this->n = g.n;
            this->m = g.m;

            if(!this->l.empty())
                l.clear();

            for(int i = 0; i < g.n; ++i)
                l.push_back(g.l[i]);
     }

     return *this;
}


///citire - afisare
ostream& Graph::print(ostream& out) const{
  int indx = 0;

  fout<<n<<" "<<m<<"\n";

  for(auto i = l.begin(); i != l.end(); ++i){
      fout<<++indx<<": ";
      for(auto j = (*i).begin(); j != (*i).end(); ++j)
        fout<<*j<<" ";
      fout<<" \n";
  }
  return out;
}

istream& Graph::read(istream& in){
    fin>>n>>m;
    return in;
}

istream& operator>>(istream& in, Graph& obj){
    obj.read(in);
    return in;
}

ostream& operator<<(ostream& out, Graph& obj){
    obj.print(out);
    return out;
}


/// destructor
Graph :: ~Graph(){
    if(!this->l.empty())
        l.clear();
}


/// metode
void Graph::do_dfs(int start, vector<bool> &viz, bool print){
    if(print)fout<<start<<" ";
    viz[start - 1] = 1;
    for(auto it = l[start - 1].begin(); it != l[start - 1].end(); ++it)
        if(!viz[*it - 1])
            do_dfs(*it, viz, print);

}

void Graph::dfs(int start){
    vector<bool> viz(n, 0);
    do_dfs(start, viz, 1);
}

void Graph::bfs(int start, vector<int>& dist){
    queue<int> q;
    vector<bool> viz(n,0);

    viz[start - 1] = 1;
    q.push(start - 1);
    dist[start - 1] = 1;
    while(!q.empty()){
        int k = q.front();

           for(auto i: l[k])
            if(viz[i - 1] == 0){
               viz[i - 1] = 1;
               dist[i - 1] = dist[k] + 1;
               q.push(i - 1);

           }

            //fout<<k + 1<<" ";
        q.pop();
    }
}

void Graph :: dist_from_node (int start){
    vector<int>dist(n, 0);
    bfs(start, dist);

    for(int i = 0; i < n; i ++)
        cout<<dist[i] - 1<<" ";
}

int Graph :: num_of_components(){
    int ct = 0;
    vector<bool> viz(n, 0);

    for(int i = 1; i <= n; ++i){
        if(!viz[i - 1]){
            ct++;
            do_dfs(i, viz, 0);
        }
    }
    return ct;
}

class UnorientedGraph : public Graph{

public:
    UnorientedGraph(int n = 1, int m = 0) : Graph(n, m) {};
    UnorientedGraph(int n, int m, vector<pair<int, int> > v);
    istream& read(istream& in) override;

};

UnorientedGraph :: UnorientedGraph(int n, int m, vector<pair<int, int> > v) : Graph(n, m){
    for(auto it : v){
        l[it.first - 1].push_back(it.second);
        l[it.second - 1].push_back(it.first);
    }
}

istream& UnorientedGraph::read(istream& in){
    Graph::read(in); /// apelam intai citrea din baza
    UnorientedGraph temp(n, m);

    for(int i = 1; i <= m; i ++){
        int x, y;
        fin>>x>>y;
        temp.l[x - 1].push_back(y);
        temp.l[y - 1].push_back(x);
    }

    *this = temp;
    return in;
}




class OrientedGraph : public Graph{

public:
    OrientedGraph(int n = 1, int m = 0) : Graph(n, m) {};
    OrientedGraph(int n, int m, vector<pair<int, int> > v);
    istream& read(istream& in) override;

};


OrientedGraph :: OrientedGraph(int n, int m, vector<pair<int, int> > v) : Graph(n, m){
    for(auto it : v){
        l[it.first - 1].push_back(it.second);
    }
}

istream& OrientedGraph::read(istream& in){
    Graph::read(in); /// apelam intai citrea din baza
    OrientedGraph temp(n, m);

    for(int i = 1; i <= m; i ++){
        int x, y;
        cin>>x>>y;
        temp.l[x - 1].push_back(y);
    }

    *this = temp;
    return in;
}


void Citire(OrientedGraph &g, int &x){
    int n, m;
    vector<pair<int, int> > v;
    fin>>n>>m>>x;
    for(int i = 1; i <= m; i ++){
        int x, y;
        fin>>x>>y;
        v.push_back(make_pair(x, y));
    }

    OrientedGraph temp(n, m, v);
    g = temp;

}

int main()
{   int x;
    OrientedGraph g;
    Citire(g, x);
    g.dist_from_node(x);
    return 0;
}