#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <limits>
#include <numeric>
#include <optional>
#include <queue>
#include <stdexcept>
#include <utility>
#include <vector>

using Edge = std::pair<std::size_t, std::size_t>;
using Order = std::vector<std::size_t>;

std::optional<Order> topological_sort(
    std::size_t n, const std::vector<Edge>& edges) {
    std::vector<std::vector<std::size_t>> out(n);
    std::vector<std::size_t> indegree(n, 0);
    for (const auto& edge : edges) {
        const auto u = edge.first, v = edge.second;
        if (u >= n || v >= n) throw std::out_of_range("vertex id");
        if (indegree[v] == std::numeric_limits<std::size_t>::max())
            throw std::overflow_error("indegree");
        out[u].push_back(v);
        ++indegree[v];
    }

    std::queue<std::size_t> ready;
    for (std::size_t v = 0; v < n; ++v)
        if (indegree[v] == 0) ready.push(v);

    Order order;
    order.reserve(n);
    while (!ready.empty()) {
        const auto u = ready.front();
        ready.pop();
        order.push_back(u);
        for (const auto v : out[u]) {
            assert(indegree[v] > 0);
            --indegree[v];
            if (indegree[v] == 0) ready.push(v);
        }
    }
    if (order.size() != n) return std::nullopt;
    return order;
}

bool valid_order(std::size_t n, const std::vector<Edge>& edges,
                 const Order& order) {
    if (order.size() != n) return false;
    std::vector<std::size_t> position(n, n);
    for (std::size_t i = 0; i < n; ++i) {
        if (order[i] >= n || position[order[i]] != n) return false;
        position[order[i]] = i;
    }
    for (const auto& edge : edges) {
        if (edge.first >= n || edge.second >= n) return false;
        if (position[edge.first] >= position[edge.second]) return false;
    }
    return true;
}

// Independent oracle for small graphs: try every vertex permutation.
bool brute_has_order(std::size_t n, const std::vector<Edge>& edges) {
    Order order(n);
    std::iota(order.begin(), order.end(), std::size_t{0});
    do {
        if (valid_order(n, edges, order)) return true;
    } while (std::next_permutation(order.begin(), order.end()));
    return false;
}

void check(std::size_t n, const std::vector<Edge>& edges) {
    const auto result = topological_sort(n, edges);
    assert(result.has_value() == brute_has_order(n, edges));
    if (result) assert(valid_order(n, edges, *result));
}

int main() {
    check(0, {});
    check(4, {});
    check(4, {{0, 1}, {0, 1}, {1, 2}});
    check(3, {{0, 1}, {1, 0}, {1, 2}});
    check(1, {{0, 0}});

    // All 2^9 directed graphs on three vertices, including self-loops.
    for (unsigned mask = 0; mask < (1u << 9); ++mask) {
        std::vector<Edge> edges;
        for (std::size_t u = 0; u < 3; ++u)
            for (std::size_t v = 0; v < 3; ++v)
                if ((mask & (1u << (u * 3 + v))) != 0)
                    edges.emplace_back(u, v);
        check(3, edges);
    }

    bool rejected = false;
    try {
        (void)topological_sort(2, {{0, 2}});
    } catch (const std::out_of_range&) {
        rejected = true;
    }
    assert(rejected);
    std::cout << "topological sort: all assertions passed\n";
}