问题 6406 --龙哥的聊天室

6406: 龙哥的聊天室★★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 7  解决: 3
[提交][状态][命题人:]

题目描述

龙哥创建的聊天室中有n人在进行发帖聊天，其中k个人做了截图，每个截图中截图者都在第一位置，其后顺序按照发帖时间前后确定。设发帖顺序为[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,表示有T (1≤T≤10000)组测试样例。
每组测试样例的第一行为两个整数n和k(1≤k≤n≤200000,n*k≤200000),分别表示聊天室人数与截图的数量。
接下去的k行。每行为一个截图，每个截图有n个整数，为1~n的一个排列（即每个整数取值范围1~n,并且这n个整数各不相等）。
测试数据保证所有的n*k之和不超过200000。

输出

每组测试数据输出一行，若这些聊天室截图是自洽的，则输出YES,否则输出NO。 
样例输入
Copy
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
样例输出
Copy
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO

提示

来源

 

[提交][状态]