聊天截图

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

编程竞赛群聊中有 $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 或 NO。

样例输入 1

10
5 1
1 2 3 4 5
4 4
1 2 3 4
2 3 1 4
3 2 1 4
4 2 3 1
6 2
1 3 5 2 4 6
6 3 5 2 1 4
3 3
1 2 3
2 3 1
3 2 1
10 2
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
1 1
1
5 2
1 2 3 5 4
2 1 3 5 4
3 3
3 1 2
2 3 1
1 3 2
5 4
3 5 1 4 2
2 5 1 4 3
1 5 4 3 2
5 1 4 3 2
3 3
1 3 2
2 1 3
3 2 1

样例输出 1

YES
YES
YES
YES
NO
YES
YES
YES
YES
NO

数据范围

对于所有测试数据，$1\le t\le10000$，$1\le k\le n\le200000$，$nk\le200000$。每一行均为 $1$ 至 $n$ 的一个排列，且不同截图的作者互不相同。一个输入文件内所有测试用例的 $nk$ 之和不超过 $200000$。