# [题解] 2023 CCPC 华为云计算挑战赛博弈，启动！ [BFS]

# 题目大意

给定一个有向二分图，分为 $G$ 部分和 $Y$ 部分，有一个棋子位于图上任意一节点。当棋子在 $G$ 部分时，玩家 $GG$ 沿节点出边操作棋子；当棋子在 $Y$ 部分时，玩家 $YY$ 沿出边操作棋子。循环往复该过程，直至棋子到达的节点没有出边。 $GG$ 的目标是让棋子在图上每个节点经过无穷次， $YY$ 的目标与之相反。两人均采取最优策略，问 $GG$ 是否有必胜策略。

# 题解

先来剖析一下题目的意思， $GG$ 获胜的条件是：从任意一点出发，棋子能经过且能无穷次经过每一个节点。
我们将每个节点分开考虑，对于每个节点 $v$ ，从任意节点出发，无论 $YY$ 如何操作， $GG$ 都能合适地操作，使棋子一定能到达 $v$ 。若所有节点都一定能到达 $v$ ，那么显然可以无穷次到达任意节点。
假设当前棋子在 $G$ 部分的节点 $g$ 上，那么：只要是 $g$ 连出的点的可到达点，也一定是 $g$ 的可到达点。
假设当前棋子在 $Y$ 部分的节点 $y$ 上，那么：只有是 $y$ 连出所有的点均可到达的点，才能是 $y$ 的可到达点。
对于每个节点 $v$ ，从 $v$ 出发，我们要传递上述的可到达关系。像最短路那样，我们倒序跑 $bfs$ 即可。

# 代码

	#include<cstdio>
	#include<vector>
	#include<queue>
	#include<bitset>

	const int MAXN=601;

	int T,N,M;
	std::bitset<MAXN> to[MAXN];
	std::vector<int> ito[MAXN];
	std::bitset<MAXN> reach;
	std::queue<int> q;

	void bfs(int S){
	reach.reset();
	while(q.size())
	q.pop();
	q.push(S);
	reach[S]=1;
	while(q.size()){
	int x=q.front();
	q.pop();
	for(int tt:ito[x])if(!reach[tt]){
	if(tt>N){
	if((to[tt]&reach)==to[tt]){
	reach[tt]=1;
	q.push(tt);
	}
	}
	else{
	reach[tt]=1;
	q.push(tt);
	}
	}
	}
	}

	inline void add(const int &x,const int &y){
	to[x][y]=1;
	ito[y].push_back(x);
	}

	int main(){
	scanf("%d",&T);
	while(T--){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N+M;++i)
	to[i].reset(),ito[i].clear();
	for(int x=1;x<=N;++x){
	int n,y;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
	scanf("%d",&y);
	add(x,N+y+1);
	}
	}
	for(int x=1;x<=M;++x){
	int n,y;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
	scanf("%d",&y);
	add(N+x,y+1);
	}
	}
	for(int i=1;i<=N+M;++i){
	bfs(i);
	if(reach.count()!=N+M){
	printf("No\n");
	goto Cont;
	}
	}
	printf("Yes\n");
	Cont:;
	}
	}