← 返回比赛

已结束 “码王杯”黑龙江工程学院第十届程序设计竞赛

← 上一题下一题 →

A1802 | $序列X$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

现在给你一个序列 $x$，包含 $n$ 个不重复的数 $a_i(1 \leq a_i \leq n)$，你可以将 $x$ 序列中任意一个数移动到序列的头部，变成一个新的序列。 如序列：$1,3,4,2,5$。移动 $1$ 到头部，序列不变，移动 $3$ 移动到头部变为 $3,1,4,2,5$，移动 $4$ 移动到头部变为 $4,1,3,2,5$，移动 $2$ 到头部变为 $2,1,3,4,5$，移动 $5$ 到头部变为 $5,1,3,4,2$，这些变化后的序列都能由原序列得到，这里的变化是指原序列变化一次后得到的。 但是很可惜，我刚刚给你序列 $x$，你就弄丢了。 现在给你 $k$ 个序列，请问是否存在一个序列 $x$，换句话说这 $k$ 个序列可以由 $x$ 序列得到。

输入格式

第一行输入 $t$ ($1 \le t \le 10^4$)，代表有 $t$ 组测试用例。 对于每组测试用例，第一行输入 $n$ 与 $k$ ($1 \le k \le n \le 2 \cdot 10^5$)，表示序列的长度为 $n$，有 $k$ 组序列，接下来 $k$ 行，每行包含 $n$ 个数 $a_i(1 \leq a_i \leq n)$，且不重复。 保证所有测试用例的 $n \cdot k$ 总和不超过 $2 \cdot 10^5$。

输出格式

如果存在 $x$ 序列则输出 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

C++ 编辑器

输入

输出