#include <iostream>
#include <vector>
#include <queue>

class Graf {
private:
    int n;
    bool orientat;
    std::vector<std::vector<int>> muchii;
public:
    explicit Graf(int size, bool o, const std::vector<std::vector<int>>& m);
    void listaDeAdiacenta();
    void transpus();
    std::vector<int> bipartit();
    std::vector<int> sortareTopologica();
    std::vector<int> componenteConexe();
};

Graf::Graf(int size, bool o, const std::vector<std::vector<int>> &m) : n(size), orientat(o), muchii(m) {}

void Graf::listaDeAdiacenta() {
    std::vector<std::vector<int>> lista(n);
    for (auto &m : muchii) {
        lista[m[0]].push_back(m[1]);
        if (!orientat)
            lista[m[1]].push_back(m[0]);
    }
    muchii = lista;
}

void Graf::transpus() {
    std::vector<std::vector<int>> transpose(n);

    for (int i = 0; i < n; i++) {
        for (auto &vec : muchii[i]) {
            transpose[vec].push_back(i);
        }
    }

    muchii = transpose;
}

std::vector<int> Graf::bipartit() {
    std::vector<int> visited(n, 0);
    std::vector<int> colors(n, 0);

    for (int i = 0; i < n; i++) {
        if(visited[i])
            continue;
        visited[i] = 1;
        std::queue<int> q; q.push(i);

        while(!q.empty()) {
            int crt = q.front(); q.pop();
            for (auto &vec : muchii[crt]) {
                if (!visited[vec]) {
                    visited[vec] = 1; colors[vec] = !colors[crt];
                    q.push(vec);
                }
                else if (colors[crt] == colors[vec]) {
                    return {};
                }
            }
        }
    }
    return colors;
}

std::vector<int> Graf::sortareTopologica() {
    std::vector<int> visited(n, 0);
    std::vector<int> degree(n, 0);
    std::vector<int> topSort;
    std::queue<int> q;

    for (auto &list : muchii) {
        for (auto &elem : list) {
            degree[elem]++;
        }
    }

    for (int i = 0; i < n; i++)
        if(!degree[i])
            q.push(i);

    while(!q.empty()) {
        int crt = q.front(); q.pop();
        topSort.push_back(crt);
        for (auto &vec : muchii[crt]) {
            degree[vec]--;
            if (!degree[vec]) {
                q.push(vec);
            }
        }
    }

    return topSort;
}

std::vector<int> Graf::componenteConexe() {
    std::vector<int> component(n, 0);
    int comp = 0;
    std::queue<int> q;

    for (int i = 0; i < 26; i++) {
        if(component[i])
            continue;

        comp++;
        q.push(i);

        while(!q.empty()) {
            int crt = q.front(); q.pop();
            component[crt] = comp;
            for (auto &vec : muchii[crt]) {
                if(!component[vec]) {
                    q.push(vec);
                }
            }
        }
    }

    return component;
}


int main() {
    std::vector<std::vector<int>> prerequisites = {{1,0},{2,0},{3,1},{3,2}};
    std::vector<std::vector<int>> safer = {{1,2}, {2,3},{5},{0},{5},{},{}};

    Graf schedule(4, true, prerequisites);
    schedule.listaDeAdiacenta();
    schedule.transpus();
    std::vector<int> yipi = schedule.sortareTopologica();
    for (auto &elem : yipi) {
        std::cout << elem << ' ';
    }

    Graf findsafe(safer.size(), true, safer);
    findsafe.transpus();
    yipi = findsafe.sortareTopologica();
    for (auto &elem : yipi) {
        std::cout << elem << ' ';
    }
    return 0;
}