#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();
    int bfs(int start, int finish);

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

};

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]);
            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
}

int Graf::bfs(int start, int finish) {
    if(start == finish) return 0;

    const int n = m_nrNodes + 1;

    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;
            }
        }
    }
    if(!visited[finish]) return -1;

    int steps = 0;
    for(int i = finish; i != 0; i = prev[i]){
        steps++;
    }

    return steps - 1;
}

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);
    for(int i = 1; i <= n; i++){
        fout<<graf.bfs(2, i)<<" ";
    }
}

int main() {

    bfsInfoArena();

    return 0;
}