#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();
    vector<vector<int>> biconnectedComponents();
    vector<int> topSort();

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);
    void biconnectedComponentsDFS(int u, vector<int> &disc, vector<int> &low, vector<edge> &st, vector<int> &parent, vector<vector<int>> &result);
    int dfsTop(int idx, int crtNode, vector<bool> &visited, vector<int> &result);
};

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() {//ar trebui mai degraba sa tina de dfs infoarena cred, dar vad eu
    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);
        }
    }
}

vector<vector<int>> Graf::biconnectedComponents() {
    vector<int> disc, low, parent;
    vector<edge> st;

    // Initialize disc and low, and parent arrays
    for (int i = 0; i <= m_nrNodes; i++) {
        disc.push_back(-1);
        low.push_back(-1);
        parent.push_back(-1);
    }

    vector<vector<int>> result;

    for (int i = 1; i <= m_nrNodes; i++) {
        if (disc[i] == -1)
            biconnectedComponentsDFS(i, disc, low, st, parent, result);

        vector<int> component;

        int j = 0;
        // If stack is not empty, pop all edges from stack
        while (!st.empty()) {
            j = 1;
            bool isFrom = false, isTo = false;
            for(int node : component){
                if(node == st.back().to){
                    isTo = true;
                }
                if(node == st.back().from){
                    isFrom = true;
                }
            }
            if(!isFrom && !isTo){
                component.push_back(st.back().to);
            }
            else if(isFrom && !isTo){
                component.push_back(st.back().to);
            }
            else if(!isFrom && isTo){
                component.push_back(st.back().from);
            }
            st.pop_back();
        }
        if (j == 1) {
            result.push_back(component);
        }
    }

    return result;
}

void Graf::biconnectedComponentsDFS(int u, vector<int> &disc, vector<int> &low, vector<edge> &st, vector<int> &parent, vector<vector<int>> &result) {
    static int time = 0;

    // Initialize discovery time and low value
    disc[u] = low[u] = ++time;
    int children = 0;

    // Go through all vertices adjacent to this
    for (auto v : m_adjacencyList[u]) {

        // If v is not visited yet, then recur for it
        if (disc[v] == -1) {
            children++;
            parent[v] = u;
            // store the edge in stack
            edge crtEdge{u, v, 0};
            st.push_back(crtEdge);
            biconnectedComponentsDFS(v, disc, low, st, parent, result);

            // Check if the subtree rooted with 'v' has a
            // connection to one of the ancestors of 'u'
            if(low[u] > low[v]) low[u] = low[v];

            vector<int> component;
            // If u is an articulation point,
            // pop all edges from stack till u -- v
            if ((disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u])) {
                while (st.back().from != u || st.back().to != v) {
                    bool isFrom = false, isTo = false;
                    for(int node : component){
                        if(node == st.back().to){
                            isTo = true;
                        }
                        if(node == st.back().from){
                            isFrom = true;
                        }
                    }
                    if(!isFrom && !isTo){
                        component.push_back(st.back().to);
                    }
                    else if(isFrom && !isTo){
                        component.push_back(st.back().to);
                    }
                    else if(!isFrom && isTo){
                        component.push_back(st.back().from);
                    }
                    st.pop_back();
                }
                bool isFrom = false, isTo = false;
                for(int node : component){
                    if(node == st.back().to){
                        isTo = true;
                    }
                    if(node == st.back().from){
                        isFrom = true;
                    }
                }
                if(!isFrom && !isTo){
                    component.push_back(st.back().to);
                }
                else if(isFrom && !isTo){
                    component.push_back(st.back().to);
                }
                else if(!isFrom && isTo){
                    component.push_back(st.back().from);
                }
                st.pop_back();
                result.push_back(component);
            }
        }

        else if (v != parent[u]) {
            if(low[u] > low[v]) low[u] = low[v];

            if (disc[v] < disc[u]) {
                edge crtEdge{u, v, 0};
                st.push_back(crtEdge);
            }
        }
    }
}

vector<int> Graf::topSort() {
    vector<bool> visited;
    for(int i = 0; i <= m_nrNodes; i++){
        visited.push_back(false);
    }
    vector<int> result;
    result.resize(m_nrNodes);
    int idx = m_nrNodes - 1;

    for(int i = 1; i <= m_nrNodes; i++){
        if(!visited[i]){
            idx = dfsTop(idx, i, visited, result);
        }
    }

    return result;
}

int Graf::dfsTop(int idx, int crtNode, vector<bool> &visited, vector<int> &result) {
    visited[crtNode] = true;

    for(int i : m_adjacencyList[crtNode]){
        if(!visited[i]){
            idx = dfsTop(idx, i, visited, result);
        }
    }

    result[idx] = crtNode;
    return idx - 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);
    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();
}

void biconexInfoArena(){
    ifstream fin("biconex.in");
    ofstream fout("biconex.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);
    vector<vector<int>> componenteBiconexe = graf.biconnectedComponents();
    fout<<componenteBiconexe.size()<<'\n';
    for(auto i: componenteBiconexe){
        for(auto j : i){
            fout<<j<<" ";
        }
        fout<<'\n';
    }
}

void sortaretInfoArena(){
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.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, true, la);
    vector<int> sortare = graf.topSort();
    for(auto i: sortare){
        fout<<i<<" ";
    }
}

int main() {

    sortaretInfoArena();

    return 0;
}