311084: CF1931F. Chat Screenshots

F. Chat Screenshotstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are $n$ people in the programming contest chat. Chat participants are ordered by activity, but each person sees himself at the top of the list.

For example, there are $4$ participants in the chat, and their order is $[2, 3, 1, 4]$. Then

• $1$-st user sees the order $[1, 2, 3, 4]$.
• $2$-nd user sees the order $[2, 3, 1, 4]$.
• $3$-rd user sees the order $[3, 2, 1, 4]$.
• $4$-th user sees the order $[4, 2, 3, 1]$.

$k$ people posted screenshots in the chat, which show the order of participants shown to this user. The screenshots were taken within a short period of time, and the order of participants has not changed.

Your task is to determine whether there is a certain order that all screenshots correspond to.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of input test cases. The descriptions of test cases follow.

The first line of the description of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5, n \cdot k \le 2 \cdot 10^5$) — the number of chat participants and the number of participants who posted screenshots.

The following $k$ lines contain descriptions of screenshots posted by the participants.

The $i$-th row contains $n$ integers $a_{ij}$ each ($1 \le a_{ij} \le n$, all $a_{ij}$ are different) — the order of participants shown to the participant $a_{i0}$, where $a_{i0}$ — the author of the screenshot. You can show that in the screenshot description it will always be at the top of the list.

It is guaranteed that the sum of $n \cdot k$ for all test cases does not exceed $2 \cdot 10^5$. It is also guaranteed that all the authors of the screenshots are different.

Output

Output $t$ lines, each of which is the answer to the corresponding test case. As an answer, output "YES" if there exists at least one order of participants, under which all $k$ screenshots could have been obtained. Otherwise, output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

ExampleInput

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

Output

YES
YES
YES
YES
NO
YES
YES
YES
YES
NO

题目大意：
在编程竞赛的聊天室中，有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个用户在聊天中发布了截图，这些截图显示了此用户看到的参与者顺序。这些截图是在短时间内拍摄的，参与者的顺序没有改变。任务是确定是否存在一个特定的顺序，使得所有截图都与之对应。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示输入测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含两个整数n和k（1 ≤ k ≤ n ≤ 2 × 10^5, n × k ≤ 2 × 10^5），分别表示聊天参与者的数量和发布截图的参与者数量。
- 接下来的k行包含发布截图的参与者的描述。
- 第i行包含n个整数a_{ij}（1 ≤ a_{ij} ≤ n，所有a_{ij}都不同），表示参与者a_{i0}看到的参与者顺序，其中a_{i0}是截图的作者。在截图描述中，他总是位于列表顶部。
- 保证所有测试用例的n × k之和不超过2 × 10^5。还保证所有截图的作者都是不同的。

输出：
- 输出t行，每行是对应测试用例的答案。如果存在至少一个参与者顺序，使得所有k个截图都可以获得，则输出"YES"。否则，输出"NO"。
- 答案可以是任何大小写形式，例如"yEs"、"yes"、"Yes"和"YES"都将被视为肯定响应。题目大意： 在编程竞赛的聊天室中，有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个用户在聊天中发布了截图，这些截图显示了此用户看到的参与者顺序。这些截图是在短时间内拍摄的，参与者的顺序没有改变。任务是确定是否存在一个特定的顺序，使得所有截图都与之对应。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示输入测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含两个整数n和k（1 ≤ k ≤ n ≤ 2 × 10^5, n × k ≤ 2 × 10^5），分别表示聊天参与者的数量和发布截图的参与者数量。 - 接下来的k行包含发布截图的参与者的描述。 - 第i行包含n个整数a_{ij}（1 ≤ a_{ij} ≤ n，所有a_{ij}都不同），表示参与者a_{i0}看到的参与者顺序，其中a_{i0}是截图的作者。在截图描述中，他总是位于列表顶部。 - 保证所有测试用例的n × k之和不超过2 × 10^5。还保证所有截图的作者都是不同的。 输出： - 输出t行，每行是对应测试用例的答案。如果存在至少一个参与者顺序，使得所有k个截图都可以获得，则输出"YES"。否则，输出"NO"。 - 答案可以是任何大小写形式，例如"yEs"、"yes"、"Yes"和"YES"都将被视为肯定响应。