CF1931F Chat Screenshots

编程竞赛群聊中有 $n$ 个人。群聊成员按活跃度排序，但每个人在自己看到的列表中都会把自己排在最前面。 例如，群聊中有 $4$ 个成员，他们的顺序为 $[2, 3, 1, 4]$。那么： - 第 $1$ 号用户看到的顺序是 $[1, 2, 3, 4]$。 - 第 $2$ 号用户看到的顺序是 $[2, 3, 1, 4]$。 - 第 $3$ 号用户看到的顺序是 $[3, 2, 1, 4]$。 - 第 $4$ 号用户看到的顺序是 $[4, 2, 3, 1]$。 有 $k$ 个人在群聊中发了截图，截图中显示了该用户看到的成员顺序。所有截图都是在很短的时间内拍摄的，成员的顺序没有发生变化。 你的任务是判断是否存在某种成员顺序，使得所有 $k$ 个截图都可能是基于该顺序得到的。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^5, n \cdot k \le 2 \cdot 10^5$），分别表示群聊成员数量和发截图的成员数量。 接下来的 $k$ 行，每行包含 $n$ 个整数 $a_{ij}$（$1 \le a_{ij} \le n$，所有 $a_{ij}$ 均不同），表示第 $i$ 个截图中成员的顺序，其中 $a_{i0}$ 是截图的作者。可以保证在截图描述中，作者总是在列表的最前面。 保证所有测试用例的 $n \cdot k$ 之和不超过 $2 \cdot 10^5$。保证所有截图的作者均不相同。

输出 $t$ 行，每行对应一个测试用例的答案。如果存在至少一种成员顺序，使得所有 $k$ 个截图都可能是基于该顺序得到的，输出 "YES"；否则输出 "NO"。 你可以以任意大小写输出答案。例如，"yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答。

由 ChatGPT 4.1 翻译