#include <bits/stdc++.h>
using namespace std;

vector<int> topo_sort(int n, vector<vector<int>>& adj) {
    vector<int> in_degree(n + 1, 0);
    for (int u = 1; u <= n; ++u)
        for (int v : adj[u])
            in_degree[v]++;

    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (in_degree[i] == 0)
            q.push(i);

    vector<int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (int v : adj[u]) {
            if (--in_degree[v] == 0)
                q.push(v);
        }
    }

    if (topo.size() < n)
        throw runtime_error("Graph has a cycle");

    return topo;
}

void dfs(int u, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& st) {
    visited[u] = true;
    for (int v : adj[u])
        if (!visited[v])
            dfs(v, adj, visited, st);
    st.push(u);
}

vector<int> topo_sort_dfs(int n, vector<vector<int>>& adj) {
    vector<bool> visited(n + 1, false);
    stack<int> st;
    for (int i = 1; i <= n; ++i)
        if (!visited[i])
            dfs(i, adj, visited, st);

    vector<int> topo;
    while (!st.empty()) {
        topo.push_back(st.top());
        st.pop();
    }
    return topo;
}