#include <iostream>
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

class Graf{
public:
    struct edge{
        int from;
        int to;
        int cost;
    };
    Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList);
    Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList, bool isCostGraph);
    void test();
    vector<int> bfs(int start);
    int dfs();

private:
    //date membre
    int m_nrNodes;
    int m_nrEdges;
    bool m_isOriented;
    bool m_isCostGraph;
    vector<vector<int>> m_adjacencyList;
    vector<edge> m_edges;

    //functii ajutatoare
    void dfsRec(int start, vector<bool> &visited);
};

Graf::Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList) {
    m_nrNodes = nrNodes;
    m_nrEdges = nrEdges;
    m_isOriented = isOriented;
    m_isCostGraph = false;
    edge crtEdge;
    m_adjacencyList.resize(nrNodes + 1);
    for(int i = 1; i <= nrNodes; i++){
        for(int j = 0; j < adjacencyList[i].size(); j++){
            m_adjacencyList[i].push_back(adjacencyList[i][j]);
            if(!isOriented){
                m_adjacencyList[adjacencyList[i][j]].push_back(i);
            }
            crtEdge.from = i;
            crtEdge.to = adjacencyList[i][j];
            crtEdge.cost = 0;
            m_edges.push_back(crtEdge);
        }
    }
}

void Graf::test(){
    cout << m_nrNodes << " " << m_nrEdges << '\n';
    for(int i = 1; i <= m_nrNodes; i++){
        cout<<i<<": ";
        for(int j : m_adjacencyList[i]){
            cout<<j<<", ";
        }
        cout<<'\n';
    }
}

Graf::Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList, bool isCostGraph) {
    //cand ajungem la costuri
}

vector<int> Graf::bfs(int start) {
    vector<int> result;

    vector<bool> visited;
    for(int i=1; i<=m_nrNodes+1; i++){
        visited.push_back(false);
    }
    deque<int> dq;
    vector<int> prev;
    for(int i=1; i<=m_nrNodes+1; i++){
        prev.push_back(0);
    }

    dq.push_back(start);
    visited[start] = true;

    while(!dq.empty()){
        int crt = dq.front();
        dq.pop_front();
        for(int i : m_adjacencyList[crt]){
            if(!visited[i]){
                dq.push_back(i);
                visited[i] = true;
                prev[i] = crt;
            }
        }
    }

    for(int f = 1; f <= m_nrNodes; f++){
        int steps = 0;
        int lastVisited;
        for(int i = f; i != 0; i = prev[i]){
            steps++;
            lastVisited = i;
        }

        if(lastVisited != start) { result.push_back(-1); }
        else { result.push_back(steps - 1); }
    }

    return result;
}

int Graf::dfs() {
    vector<bool> visited;
    for(int i = 0; i <= m_nrNodes; i++){
        visited.push_back(false);
    }

    int nrConexComponents = 0;

    for(int i = 1; i <= m_nrNodes; i++){
        if(!visited[i]){
            nrConexComponents++;
            dfsRec(i, visited);
        }
    }

    return nrConexComponents;
}

void Graf::dfsRec(int start, vector<bool> &visited) {
    visited[start] = true;
    for(auto i : m_adjacencyList[start]){
        if(!visited[i]){
            dfsRec(i, visited);
        }
    }
}

void bfsInfoArena(){
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");

    int n, m, x, from, to;
    vector<vector<int>> la;

    fin>>n>>m>>x;

    la.resize(n+1);
    for(int i = 0; i < m; i++){
        fin>>from>>to;
        la[from].push_back(to);
    }
    Graf graf = Graf(n, m, true, la);
    vector<int> res = graf.bfs(x);
    for(int i : res){
        fout<<i<<" ";
    }
}

void dfsInfoArena(){
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");

    int n, m, from, to;
    vector<vector<int>> la;

    fin>>n>>m;

    la.resize(n+1);
    for(int i = 0; i < m; i++){
        fin>>from>>to;
        la[from].push_back(to);
    }
    Graf graf = Graf(n, m, false, la);
    fout<<graf.dfs();
}

int main() {

    dfsInfoArena();

    return 0;
}