题意简述

有 $n$ 个人，真实顺序是一个排列。
每个人看到的聊天列表是：自己放在第一位，其余人的相对顺序与真实顺序一致。

有 $k$ 个人发了截图，第 $i$ 张截图给出的是第 $a_{i0}$ 个人看到的顺序（$a_{i0}$ 总是在第一位）。

问：是否存在一个真实顺序，使得所有截图都符合规则？

问题转化

对于一张截图（作者为 $x$）：

• 第一位是 $x$，这个信息不能告诉我们 $x$ 在真实顺序中的位置（因为每个人看到的自己都在第一位）。
• 从第二位到最后一位，顺序完全等同于真实顺序中除去 $x$ 后其他人的顺序。

因此，对于每个截图，我们可以在 第二位到第 $n$ 位 之间得到若干 相对顺序约束：

若截图中第 $j$ 位是 $u$，第 $j+1$ 位是 $v$（$j \ge 1$），那么在真实顺序中，$u$ 必须在 $v$ 之前。

建模

• 建立一个有向图，顶点是 $1 \dots n$。
• 对于每张截图 $i$，对 $j = 1 \dots n-2$（即截图中的第 $2$ 位到第 $n-1$ 位）：
  • 设 $u = a[i][j],\ v = a[i][j+1]$
  • 添加有向边 $u \to v$，表示 $u$ 必须排在 $v$ 前面。

判断可行性

如果存在一个真实顺序满足所有截图，那么该顺序就是图的一个 拓扑排序。

因此，问题等价于：检查图中是否有环。

• 无环 $\Rightarrow$ 存在拓扑序 $\Rightarrow$ 答案是 "YES"
• 有环 $\Rightarrow$ 不可能满足所有约束 $\Rightarrow$ 答案是 "NO"

标程的检查方法

标程没有直接用 Kahn 算法（BFS）拓扑排序，而是用了 DFS 求退出时间 的方法来判断环：

1. 对图进行 DFS，给每个顶点记录 tout[v]（离开时间，即递归结束时的全局时间戳）。
2. 在有向无环图中，如果存在边 $u \to v$，则一定满足 tout[u] > tout[v]（因为 $u$ 要先于 $v$ 被访问并结束）。
3. 反过来，如果某条边 $u \to v$ 满足 tout[u] < tout[v]，则说明图中存在环（因为 $v$ 结束时间更晚，意味着 $v$ 在 DFS 树上先于 $u$ 被访问且尚未结束，形成后向边）。

标程在 DFS 结束后，遍历所有添加过的边，检查是否 tout[u] < tout[v]。
如果存在这样的边，输出 "NO"；否则 "YES"。

复杂度分析

• 边数：每张截图添加 $n-2$ 条边，总边数 $\le k \cdot (n-2) \le n \cdot k \le 2 \times 10^5$（题目保证）。
• 时间：DFS $O(n + m)$，检查边 $O(m)$，总复杂度 $O(n \cdot k)$，满足要求。
• 空间：邻接表存储，$O(n + m)$。

示例验证

以题目中第二个样例：

4 4
1 2 3 4
2 3 1 4
3 2 1 4
4 2 3 1

从截图 1（作者 1）：第二位开始 [2,3,4]，得 $2\to 3,\ 3\to 4$
截图 2（作者 2）：[3,1,4]，得 $3\to 1,\ 1\to 4$
截图 3（作者 3）：[2,1,4]，得 $2\to 1,\ 1\to 4$
截图 4（作者 4）：[2,3,1]，得 $2\to 3,\ 3\to 1$

图无环，输出 "YES"。

易错点

• 不要从截图的第一位（作者）建立约束，因为作者的位置在截图中是假的。
• 边可能重复，但重复边不影响判环。
• 所有截图作者互不相同，但这不是解题关键，只是保证输入不矛盾。
• DFS 退出时间判环的方法正确，但要注意多次 DFS（因为图可能不连通）。

总结

核心思路：

从每个截图中提取除作者外相邻元素的先后顺序，建图，检查是否有环。

结论：

• 有环 $\to$ "NO"
• 无环 $\to$ "YES"

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int timer = 0;

void dfs(int v, vector<vector<int>> &g, vector<bool> &vis, vector<int> &tout) {
    vis[v] = true;
    for (int u : g[v]) {
        if (!vis[u]) {
            dfs(u, g, vis, tout);
        }
    }
    tout[v] = timer++;
}

void solve() {
    timer = 0;
    int n, k;
    cin >> n >> k;
    
    vector<vector<int>> a(k, vector<int>(n));
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
            a[i][j]--;
        }
    }
    
    vector<vector<int>> g(n);
    for (int i = 0; i < k; ++i) {
        for (int j = 1; j + 1 < n; ++j) {
            int u = a[i][j];
            int v = a[i][j + 1];
            g[u].push_back(v);
        }
    }
    
    vector<int> tout(n, -1);
    vector<bool> vis(n, false);
    
    for (int i = 0; i < n; ++i) {
        if (!vis[i]) {
            dfs(i, g, vis, tout);
        }
    }
    
    for (int i = 0; i < k; ++i) {
        for (int j = 1; j + 1 < n; ++j) {
            int u = a[i][j];
            int v = a[i][j + 1];
            if (tout[u] < tout[v]) {
                cout << "NO";
                return;
            }
        }
    }
    
    cout << "YES";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        solve();
        cout << "\n";
    }
    
    return 0;
}