← 返回题目列表

Codeforces · 1931/F

F. 聊天截图

中文机器翻译题面 查看原题

编程竞赛聊天中有 $$$n$$$ 人。聊天参与者按活动排序,但每个人都将自己视为列表的顶部。

例如,聊天中有 $$$4$$$ 参与者,他们的顺序是 $$$[2, 3, 1, 4]$$$。然后

- $$$1$$$-st 用户看到订单 $$$[1, 2, 3, 4]$$$。
- $$$2$$$-第一个用户看到订单 $$$[2, 3, 1, 4]$$$。
- $$$3$$$-rd 用户看到订单 $$$[3, 2, 1, 4]$$$。
- 第 $$$4$$$ 位用户看到订单 $$$[4, 2, 3, 1]$$$。

$$$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$$$ 行包含参与者发布的屏幕截图的描述。

第 $$$i$$$ 行包含 $$$n$$$ 个整数 $$$a_{ij}$$$($$$1 \le a_{ij} \le n$$$,所有 $$$a_{ij}$$$ 都不同) — 显示给参与者 $$$a_{i0}$$$ 的参与者顺序,其中 $$$a_{i0}$$$ — 作者屏幕截图。您可以在屏幕截图描述中表明它始终位于列表的顶部。

保证所有测试用例的 $$$n \cdot k$$$ 之和不超过 $$$2 \cdot 10^5$$$。还保证所有截图的作者都是不同的。

输出

输出$$$t$$$行,每一行都是对应测试用例的答案。作为答案,如果存在至少一个参与者顺序,则输出“YES”,在该顺序下可以获得所有 $$$k$$$ 屏幕截图。否则,输出“NO”。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #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