CF925

补题ing 待更新

F

对第2到n依次建边，求拓扑序是否存在，即cnt=n

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N=2e5+5;
int a[N],rd[N],n,cnt;
vector<int>e[N];
bool tuopu(){
    //这里可以就用普通队列
	priority_queue<int,vector<int>,greater<int>>q;
	cnt=0;
	for(int i=1;i<=n;i++){
		if(rd[i]==0) q.push(i);
	}
	while(!q.empty()){
		int x=q.top();
		q.pop();
		for(auto t:e[x]){
			rd[t]--;
			if(rd[t]==0) q.push(t);
		}
		cnt++;
	}
	return cnt==n;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int t,x,k,ans=0;cin>>t;
	while(t--){
		cin>>n>>k;
		//注意用memset初始化会t 
		for(int i=1;i<=n;i++){
			e[i].clear();
			rd[i]=0;
		}
		while(k--){
			for(int i=1;i<=n;i++){
				cin>>a[i];
				if(i>=3){
					e[a[i]].push_back(a[i-1]);
					rd[a[i-1]]++;
				}
			}
			
		}
		if(tuopu()){
			cout<<"YES";
		}
		else cout<<"NO";
		cout<<endl;
	}
	return 0;
}