拓扑排序

// 标准答案 —— 不用队列、不用入度数组，每一轮从头扫一遍
//
// 输入：第一行 n m（n 个任务、m 条依赖），接下来 m 行 `u v`，意思是「u 必须排在 v 前面」
//       ⚠ 可能有重边，也可能有自环（自环 = 「我必须排在我自己前面」= 无解）
// 输出：排不出来（有环）就输出 -1；否则输出**字典序最小**的那个合法顺序
//
// 这份代码的想法朴素得不能再朴素：
//   一轮一轮地挑人。每一轮扫描所有还没被挑走的任务，
//   看它的**前驱是不是全都已经被挑走了** —— 是的话它现在就可以做；
//   在所有「现在就可以做」的任务里，挑**编号最小**的那个。
//   某一轮下来一个都挑不出来 → 剩下的这些人互相卡住 → 有环 → -1。
//
// 它慢在哪：每挑一个人都要把整张图重新扫一遍，O(n × (n + m))。
// 但它对得刺眼 —— **「可以做」这件事它是每次现算的**，
// 而 fast.cpp 的入度数组是**增量维护**的（减一、减一、减到 0）。
// 一个现算、一个增量维护，两个思路完全不同，这正是对拍要的
// （第 9 章那条规矩：同一个思路写两遍只能验出打字错误）。
//
// ★ 为什么答案要规定成「字典序最小」：拓扑序通常**不唯一**，
//   而对拍是逐字节比字符串的。不把答案钉成唯一的，两份都对的程序也会被判成不一致。
//   正文第 5 步专门讲了这件事，那里还有 count.cpp 数出这张图到底有多少个合法顺序。

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

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> pre(n + 1);          // pre[v] = v 的所有前驱（可能重复，不去重）
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        pre[v].push_back(u);
    }

    vector<char> done(n + 1, 0);
    vector<int> ans;
    for (int step = 0; step < n; step++) {
        int pick = -1;
        for (int v = 1; v <= n && pick < 0; v++) {
            if (done[v]) continue;
            bool ready = true;               // ★ 每一轮都重新问一遍「它的前驱都走完了吗」
            for (int u : pre[v])
                if (!done[u]) { ready = false; break; }
            if (ready) pick = v;             // v 从小到大扫，第一个可用的就是编号最小的
        }
        if (pick < 0) { cout << -1 << "\n"; return 0; }   // 一个都挑不出来 = 有环
        done[pick] = 1;
        ans.push_back(pick);
    }

    for (int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
    return 0;
}

// 拓扑排序 —— Kahn 算法：★ 它其实就是第 30 章那个 BFS，只是「什么时候能入队」的条件变了
//
// 和 brute.cpp 解同一道题，答案必须一样，但快得多。
//
// ★ 这一章的关键一步，一句话：
//
//     BFS 里「能入队」的条件是「没来过」；
//     拓扑排序里「能入队」的条件是「**所有前驱都已经出队了**」。
//
//   而「所有前驱都出队了」这件事，不需要每次去数 —— 只要给每个点记一个 in[v]
//   （还有几个前驱没出队），每当一个前驱出队，就把它的所有后继 in 减一，
//   **谁减到 0，谁就该入队了**。
//
//   注意这句话的形状和第 21 章那句一模一样：**「依赖谁，就先填谁」**。
//   第 21 章是 DP 的填表顺序、第 26 章是区间、第 27 章是后序遍历、第 28 章是 S 从小到大，
//   这一章它终于以最直白的样子出现了 —— **拓扑序就是「依赖顺序」这四个字本身。**
//
// ★ 副产品（而且是白送的）：
//
//     队列空了，可输出的点却不够 n 个  ⇔  图里有环。
//
//   为什么：剩下的那些点，每一个都还欠着至少一个前驱；
//   顺着「谁欠谁」一直往回走，点是有限的，早晚会走回一个来过的点 —— 那就是一个环。
//   反过来，有环的话环上的点谁也别想把入度减到 0。**判环不用另写一份代码。**
//
// ⚠ 这里用的是**小根堆**而不是普通队列，因为题目要「字典序最小」的那个答案。
//   换成普通 queue 也能得到一个**合法**的拓扑序 —— 只是不一定是字典序最小的那个。
//   拓扑序通常不唯一，这是本教材第一道答案不唯一的题，正文第 5 步专门讲。
//
// 复杂度：每条边只被处理一次，每个点进出堆各一次 → O((n + m) log n)。
//         （不要字典序最小的话用普通队列，就是 O(n + m)。）

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

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);            // g[u] = u 指向的那些点（有向图只存一遍！）
    vector<int> in(n + 1, 0);                // in[v] = 还有几个前驱没出队

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        in[v]++;                             // ★ 入度加在**箭头指向**的那一头
    }

    // 一开始就没有任何前驱的点，直接入队
    priority_queue<int, vector<int>, greater<int>> q;   // 小根堆 = 每次取编号最小的
    for (int v = 1; v <= n; v++)
        if (in[v] == 0) q.push(v);

    vector<int> ans;
    while (!q.empty()) {
        int u = q.top();
        q.pop();
        ans.push_back(u);                    // ★ 出队时才输出，不是入队时
        for (int v : g[u]) {
            if (--in[v] == 0) q.push(v);     // ★ 减到 0 才入队；没减到 0 说明它还欠着别人
        }
    }

    // ★ 队列空了却还有人没出来 —— 他们互相卡死，图里有环
    if ((int)ans.size() < n) { cout << -1 << "\n"; return 0; }

    for (int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
    return 0;
}

// 第二种拓扑排序：DFS 的**后序逆序**
//
// 这份代码存在的理由，不是「再给一种写法」，而是要制造一件事：
//   **它和 fast.cpp 给出的顺序通常不一样，但两个都对。**
//   这就是正文第 5 步那节「答案不唯一」最好的证据 —— 不是我说的，是两份代码打出来的。
//
// 想法（★ 一句话）：
//   对 u 做 DFS，把它能到达的点**全部处理完之后**，再把 u 记下来。
//   于是「u 之后才被记下来的点」，全都是 u 到不了的 —— 把这张记录表**倒过来**，
//   u 就排在所有它能到达的点前面。这正是拓扑序要的。
//
//   ★ 「递归回来之后才做事」= 后序遍历 —— 第 27 章树形 DP 那一句「依赖谁就先填谁」，
//   在这里第二次出现，而且这次是在有向图上。
//
// 判环用**三种颜色**（这是有向图判环的标准写法，和无向图的 vis 不是一回事）：
//   0 = 还没碰过
//   1 = **正在递归中**（它在当前这条路径上）
//   2 = 已经彻底处理完（连同它能到的所有点）
//   走到一个颜色为 1 的点 → 说明当前这条路绕回了自己 → **有环**。
//   ⚠ 走到颜色为 2 的点是完全正常的（只是「以前从别处来过」），不是环。
//   只用一个 vis 数组的话，这两种情况分不出来 —— 这是有向图判环的头号错误。
//
// 输出格式和 fast.cpp 一致（有环输出 -1），但顺序不保证字典序最小。
// scripts/check-viz.mjs 对它做的是**硬验证**：拿 check.cpp 逐条边检查它是不是合法拓扑序，
// 并且核对「有没有环」这个结论必须和 fast.cpp 一致。

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

int n, m;
vector<vector<int>> g;
vector<int> color;                           // 0 没碰过 / 1 正在递归中 / 2 处理完了
vector<int> post;                            // 处理完的先后顺序
bool hasCycle = false;

void dfs(int u) {
    color[u] = 1;                            // 进入：标成「正在递归中」
    for (int v : g[u]) {
        if (color[v] == 1) { hasCycle = true; return; }   // ★ 撞上路径上的点 = 环
        if (color[v] == 0) {
            dfs(v);
            if (hasCycle) return;
        }
        // color[v] == 2：以前从别处走完过它，正常，跳过
    }
    color[u] = 2;                            // 离开：它和它能到的点都处理完了
    post.push_back(u);                       // ★ 后序：递归回来之后才记
}

int main() {
    if (!(cin >> n >> m)) return 0;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }

    color.assign(n + 1, 0);
    for (int v = 1; v <= n && !hasCycle; v++)
        if (color[v] == 0) dfs(v);

    if (hasCycle) { cout << -1 << "\n"; return 0; }

    reverse(post.begin(), post.end());        // ★ 后序，倒过来
    for (int i = 0; i < n; i++) cout << post[i] << " \n"[i == n - 1];
    return 0;
}

// ✗ 错误版本二：用普通队列，而不是小根堆
//
// ★ 这一份特殊：**它给出的顺序是完全合法的拓扑序**，check.cpp 逐条边查都能通过。
//   它错的只有一件事 —— 题目要「字典序最小」的那个，而它给的是「先入队先出」的那个。
//
// 把它留下来，是因为它把这一章两件事同时点破了：
//   ① **拓扑序不唯一**：同一张图，两份都「对」的代码给出不同的答案；
//   ② 所以**题面必须把答案钉唯一**（或者改用验证器对拍）。
//      对拍是逐字节比字符串的 —— 题面含糊一点，对拍就没法做。
//
//   默认那张图上：正解 `5 3 1 6 2 4`，它给 `5 6 3 1 2 4` —— 两个都合法。
//
// ⚠ 它是否会被抓住，同样取决于生成器：
//   如果任何时刻「入度为 0 的点」都只有一个，那拓扑序本来就唯一，
//   小根堆和普通队列**给出的东西一模一样**，这份代码永远是对的。
//   一条链就是这种图。正文第 11 步有实测。
//
// 只改了一行：priority_queue → queue。

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

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> in(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        in[v]++;
    }

    queue<int> q;                            // ✗ 普通队列：先入队的先出，和编号大小无关
    for (int v = 1; v <= n; v++)
        if (in[v] == 0) q.push(v);

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

    if ((int)ans.size() < n) { cout << -1 << "\n"; return 0; }
    for (int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
    return 0;
}

// ✗ 错误版本五：在**入队**的时候就把点记进答案，而不是出队的时候
//
// 第 30 章刚讲过「vis 要在入队时打」，这一章正好反过来 ——
// **记答案必须在出队时**。两句话看着像在打架，其实说的是同一件事：
//
//     入队时打 vis：是为了「别让同一个点被塞两次」，越早越好。
//     出队时记答案：是因为**顺序是由出队决定的**，而不是由入队决定的。
//
//   ★ 用普通队列时这两者恰好一样（先进先出，入队序 = 出队序），所以这个 bug 会隐身；
//   一旦换成**小根堆**，堆会把队列里的元素重新排一遍 ——
//   「进去的顺序」和「出来的顺序」就分家了，这份代码立刻错。
//
//   这也解释了为什么它在第 30 章那种纯 BFS 里从来不出问题：那里根本没有堆。
//
// 只改了两行：ans.push_back 从出队那里挪到了入队那里。

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

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> in(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        in[v]++;
    }

    vector<int> ans;
    priority_queue<int, vector<int>, greater<int>> q;
    for (int v = 1; v <= n; v++)
        if (in[v] == 0) { q.push(v); ans.push_back(v); }   // ✗ 入队就记

    while (!q.empty()) {
        int u = q.top();
        q.pop();
        for (int v : g[u])
            if (--in[v] == 0) { q.push(v); ans.push_back(v); }   // ✗ 入队就记
    }

    if ((int)ans.size() < n) { cout << -1 << "\n"; return 0; }
    for (int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
    return 0;
}

// ✗ 错误版本三：入度减了，但没等它减到 0 就把点塞进队列
//
// 写成了：
//     --in[v];
//     q.push(v);          // ✗ 不管减完是不是 0
// 正确的是：
//     if (--in[v] == 0) q.push(v);
//
// 这一处的意思差得很远：`in[v] == 0` 的含义是「**所有**前驱都出队了」。
// 只要有一个前驱走完就把 v 放出去，等于把「必须全部满足」偷偷降级成了「满足一个就行」。
//
// 症状有两种，而且**它们看起来完全不像同一个 bug**：
//   · v 被提前输出（排在某个前驱前面）→ 顺序违法；
//   · v 被塞进队列好几次 → 输出里出现重复编号，长度还超过 n。
//   第二种正是 check.cpp 第一关（「必须是 1..n 的排列」）要拦的东西。
//
// ⚠ 有一类图完全抓不到它：**每个点最多只有一个前驱**（比如一棵树、一条链）——
//   那时「满足一个」和「满足全部」是同一句话。
//   所以生成器必须造得出「一个点被两条以上的边指着」的图。

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

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> in(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        in[v]++;
    }

    priority_queue<int, vector<int>, greater<int>> q;
    for (int v = 1; v <= n; v++)
        if (in[v] == 0) q.push(v);

    vector<int> ans;
    while (!q.empty()) {
        int u = q.top();
        q.pop();
        ans.push_back(u);
        for (int v : g[u]) {
            --in[v];
            q.push(v);                       // ✗ 没判 0 就入队
        }
        if ((int)ans.size() > n + 5) break;  // 防止死循环把输出撑爆（重复入队会越滚越多）
    }

    if ((int)ans.size() < n) { cout << -1 << "\n"; return 0; }
    for (int i = 0; i < (int)ans.size(); i++)
        cout << ans[i] << " \n"[i == (int)ans.size() - 1];
    return 0;
}

// ✗ 错误版本四：把依赖的方向整个读反了
//
//     g[v].push_back(u);   // ✗ 应该是 g[u].push_back(v);
//     in[u]++;             // ✗ 应该是 in[v]++;
//
// 也就是把题面那句「u 必须排在 v 前面」读成了「v 必须排在 u 前面」。
// 于是它老老实实地算出了**整张图反过来**之后的拓扑序 ——
// 算法一点毛病都没有，错的是**读题**。
//
// ⚠ 注意它和「只把 in 那一行写错」是两回事。只写错 in（`in[u]++` 而 g 不动）
//   得到的是一份自相矛盾的代码：初始队列装的是「没有出边的点」，
//   而它们又没有后继可减 —— 队列立刻空掉，几乎每组数据都输出 -1，
//   一眼就能看出不对。**方向读反反而更危险，因为它看起来完全正常。**
//
// ★ 这个 bug 的隐身条件很有意思，值得记住：
//   如果生成器造出来的图**反过来还是一张 DAG**（有向图基本都是），
//   它照样能输出一个「像模像样」的顺序 —— 长度对、编号不重复，
//   **check.cpp 第一关根本拦不住它**，只有第二关「每条边前面指向后面」才逮得到。
//   这正好说明验证器为什么要查两件事，而不是只查「是不是排列」。
//
// 顺带：如果生成器顺手只连「编号小 → 编号大」，那么反过来就是「大 → 小」，
// 两个方向的字典序最小拓扑序分别是 1 2 3 … 和 n … 2 1，差别巨大，反而一抓一个准。
// **这个 bug 是本章五个里唯一一个「温柔数据反而抓得到」的** —— 正文第 11 步那张表里能看到。

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

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> in(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[v].push_back(u);                   // ✗ 方向读反了
        in[u]++;                             // ✗ 于是入度也记到了另一头
    }

    priority_queue<int, vector<int>, greater<int>> q;
    for (int v = 1; v <= n; v++)
        if (in[v] == 0) q.push(v);

    vector<int> ans;
    while (!q.empty()) {
        int u = q.top();
        q.pop();
        ans.push_back(u);
        for (int v : g[u])
            if (--in[v] == 0) q.push(v);
    }

    if ((int)ans.size() < n) { cout << -1 << "\n"; return 0; }
    for (int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
    return 0;
}

// ✗ 错误版本一：忘了判环 —— 队列空了就直接把手上这些点打印出来
//
// 少的就是最后那一句 `if (ans.size() < n) 输出 -1`。
//
// 它的可怕之处在于：**只要图是 DAG，它就完全正确。**
// 只有当图里真的有环时，它才会打出一个**长度不够 n** 的序列 ——
// 而且那个序列里的每一条依赖居然都是满足的，验证器只查「前面指向后面」的话还查不出来
//（check.cpp 第一关查的就是「必须正好是 1..n 的排列」，正是为它准备的）。
//
// ★ 所以它的死活完全捏在生成器手里：
//   生成器只要顺手「只连编号小 → 编号大」的边（这是造 DAG 最省事的办法，
//   也是几乎每个人的第一反应），图就永远无环，这份代码 **0 / 300**。
//   正文第 11 步有实测。
//
// 顺带：这也是「白送的判环」最容易被漏掉的原因 ——
// 它白送到你根本注意不到自己没接住。

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

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> in(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        in[v]++;
    }

    priority_queue<int, vector<int>, greater<int>> q;
    for (int v = 1; v <= n; v++)
        if (in[v] == 0) q.push(v);

    vector<int> ans;
    while (!q.empty()) {
        int u = q.top();
        q.pop();
        ans.push_back(u);
        for (int v : g[u])
            if (--in[v] == 0) q.push(v);
    }

    // ✗ 这里少了一句：if ((int)ans.size() < n) { cout << -1 << "\n"; return 0; }
    if (ans.empty()) { cout << "\n"; return 0; }
    for (size_t i = 0; i < ans.size(); i++)
        cout << ans[i] << " \n"[i == ans.size() - 1];
    return 0;
}

// ✗ 「什么都不做」—— 判完环之后直接输出 1 2 3 … n
//
// 它不是一个真实的 bug（没人会不小心写出这个），它是一块**试金石**：
//
//   ★ **如果你的生成器连「什么都不做」都抓不住，那它什么都证明不了。**
//
// 而这块试金石专门用来打假一个特定的「顺手」写法：
// 生成器造 DAG 时只连「编号小 → 编号大」的边（这是最省事的造法，也几乎是每个人的第一反应），
// 于是数据白送了一条题目里没有的性质 —— **编号本身就是一个合法拓扑序，而且正好是字典序最小的那个**。
// 这批数据上，这份代码 **0 / 300**：它和真正的正解一个字都不差。
//
// 把生成器改成「先随机一个排列，再连 perm[i] → perm[j]」之后
// （图的形状一点没变，只是给点换了名字），它立刻 **297 / 300**。
// 正文第 11 步那张表就是这么来的。
//
// 这一处改动和第 27 章「打乱树的点编号」是同一招：
// **别让编号自己带上一层题目没给的含义。**

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

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    vector<int> in(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        in[v]++;
    }

    // 判环这一步是老老实实做的 —— 免得它连「有环」都答不上来，那就太假了
    {
        queue<int> q;
        vector<int> d = in;
        for (int v = 1; v <= n; v++) if (d[v] == 0) q.push(v);
        int out = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop(); out++;
            for (int v : g[u]) if (--d[v] == 0) q.push(v);
        }
        if (out < n) { cout << -1 << "\n"; return 0; }
    }

    // ✗ 然后就……直接按编号输出
    for (int i = 1; i <= n; i++) cout << i << " \n"[i == n];
    return 0;
}

// 拓扑排序 —— Kahn 算法：★ 它其实就是第 30 章那个 BFS，只是「什么时候能入队」的条件变了
//
// 和 brute.cpp 解同一道题，答案必须一样，但快得多。
//
// ★ 这一章的关键一步，一句话：
//
//     BFS 里「能入队」的条件是「没来过」；
//     拓扑排序里「能入队」的条件是「**所有前驱都已经出队了**」。
//
//   而「所有前驱都出队了」这件事，不需要每次去数 —— 只要给每个点记一个 in[v]
//   （还有几个前驱没出队），每当一个前驱出队，就把它的所有后继 in 减一，
//   **谁减到 0，谁就该入队了**。
//
//   注意这句话的形状和第 21 章那句一模一样：**「依赖谁，就先填谁」**。
//   第 21 章是 DP 的填表顺序、第 26 章是区间、第 27 章是后序遍历、第 28 章是 S 从小到大，
//   这一章它终于以最直白的样子出现了 —— **拓扑序就是「依赖顺序」这四个字本身。**
//
// ★ 副产品（而且是白送的）：
//
//     队列空了，可输出的点却不够 n 个  ⇔  图里有环。
//
//   为什么：剩下的那些点，每一个都还欠着至少一个前驱；
//   顺着「谁欠谁」一直往回走，点是有限的，早晚会走回一个来过的点 —— 那就是一个环。
//   反过来，有环的话环上的点谁也别想把入度减到 0。**判环不用另写一份代码。**
//
// ⚠ 这里用的是**小根堆**而不是普通队列，因为题目要「字典序最小」的那个答案。
//   换成普通 queue 也能得到一个**合法**的拓扑序 —— 只是不一定是字典序最小的那个。
//   拓扑序通常不唯一，这是本教材第一道答案不唯一的题，正文第 5 步专门讲。
//
// 复杂度：每条边只被处理一次，每个点进出堆各一次 → O((n + m) log n)。
//         （不要字典序最小的话用普通队列，就是 O(n + m)。）

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

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);            // g[u] = u 指向的那些点（有向图只存一遍！）
    vector<int> in(n + 1, 0);                // in[v] = 还有几个前驱没出队

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        in[v]++;                             // ★ 入度加在**箭头指向**的那一头
    }

    // 一开始就没有任何前驱的点，直接入队
    priority_queue<int, vector<int>, greater<int>> q;   // 小根堆 = 每次取编号最小的
    for (int v = 1; v <= n; v++)
        if (in[v] == 0) q.push(v);

    vector<int> ans;
    while (!q.empty()) {
        int u = q.top();
        q.pop();
        ans.push_back(u);                    // ★ 出队时才输出，不是入队时
        for (int v : g[u]) {
            if (--in[v] == 0) q.push(v);     // ★ 减到 0 才入队；没减到 0 说明它还欠着别人
        }
    }

    // ★ 队列空了却还有人没出来 —— 他们互相卡死，图里有环
    if ((int)ans.size() < n) { cout << -1 << "\n"; return 0; }

    for (int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
    return 0;
}