提交时间:2025-11-26 20:02:58

运行 ID: 38983

#include<bits/stdc++.h> #define int long long #define doub long double #define PII pair<int,int> #define fir first #define sec second #define PC(x) __builtin_popcountll(x) #define ctz(x) __builtin_ctzll(x) #define clz(x) __builtin_clzll(x) #define lb(x) ((x)&(-(x))) #define lc(p) ((p)<<1) #define rc(p) ((p)<<1|1) #define push_back emplace_back // #define endl '\n' using namespace std; const int N=1007; int n,m; bool vis[N]; bool in[N][N]; bitset<N> a[N]; int siz[N]; inline void slv(){ cin>>n>>m; for(int i=1;i<=n;i++)a[i].reset(),vis[i]=0; for(int i=1;i<=m;i++){ cin>>siz[i]; for(int j=1;j<=siz[i];j++){ int x;cin>>x; if(siz[i]>1)a[x][i]=1; } } for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i^j)in[i][j]=((a[i]|a[j])==a[j]); bool Ans=1; for(int r=1;r<n;r++){ int v=-1,u=-1; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j)continue; if(vis[i]||vis[j])continue; if(in[i][j]){v=i;u=j;break;} }if(v!=-1)break; } if(v==-1){Ans=0;break;}vis[v]=1; for(int i=1;i<=n;i++)in[i][v]=0; for(int i=1;i<=m;i++)if(a[v][i]&&--siz[i]==1)a[u][i]=0; for(int i=1;i<=n;i++)if((u^i)&&((a[u]|a[i])==a[i]))in[u][i]=1; } cout<<(Ans?"YES":"NO")<<endl; } signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifndef ONLINE_JUDGE freopen("1.in","r",stdin); freopen("1.out","w",stdout); #endif int T;cin>>T; while(T--)slv(); return 0; }