提供一种 DFS 的写法。

正解楼上已经说得很清楚了，在搜索过程中，每搜到一个节点判断是否有这个节点的颜色的钥匙，如果有，那么继续搜索；如果没有，就把它压进对应颜色的 vector 中。

每搜到一种颜色，也需要将对应颜色的 vector 中的元素进行搜索，搜索完成后清空数组。

其余部分与 BFS 大致相同，不再赘述。注意细节，比如第一次搜索中没有搜到的点，第二次不能再搜索等。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e5+5;
ll T,n,m,c[maxn],ky[maxn],s[maxn],f[maxn];
bool vis[maxn],col[maxn],ext[maxn];
/*
vis:是否访问到这个点
col:是否有这个颜色
ext:第一次未访问到的点（第二次不需要访问） 
*/
vector<ll> G[maxn],pre_v[maxn];
void init(){
	for(int i=1;i<=n;i++){//清空 
		c[i]=ky[i]=f[i]=0;
		vis[i]=col[i]=ext[i]=false;
		G[i].clear();
		pre_v[i].clear();
	}
}
void dfs(bool opt,ll fa){
	if(!col[ky[fa]]){//新颜色，搜索对应颜色的 vector 数组 
		col[ky[fa]]=true;
		for(auto v:pre_v[ky[fa]]){
			if(!vis[v]){
				vis[v]=true;
				dfs(opt,v);
			}
		}			
		pre_v[ky[fa]].clear();
	}
	for(auto v:G[fa]){//搜索与v连的边 
		if(vis[v] || ext[v])continue;
		if((opt && ky[v]==c[v])||col[c[v]]){
			vis[v]=true;
			dfs(opt,v);
		}else{
			pre_v[c[v]].push_back(v); 
		}
	}
}
bool ret(bool opt){
	for(int i=1;i<=n;i++){//清空 
		vis[i]=col[i]=false;
		pre_v[i].clear();
	}
	vis[1]=true;
	dfs(opt,1);
	if(!opt){
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				ext[i]=true;
			}
		}
	}	
	for(int i=1;i<=n;i++){//找到 未搜到，并且钥匙未归位的点 
		if(!vis[i] && s[i]!=f[i]){
			return false;
		}
	}
	return true;	
}
int main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&n,&m);
		init();
		for(int i=1;i<=n;i++){
			scanf("%lld",&c[i]);
		}
		for(int i=1;i<=n;i++){
			scanf("%lld",&ky[i]);
			s[i]=ky[i];
		}
		for(int i=1;i<=n;i++){
			scanf("%lld",&f[i]);
		}		
		for(int i=1;i<=m;i++){
			ll x,y;
			scanf("%lld%lld",&x,&y);
			G[x].push_back(y);
			G[y].push_back(x);
		}
		bool flag=true;
		flag&=ret(0);
		for(int i=1;i<=n;i++){
			ky[i]=f[i];
		}
		flag&=ret(1);
		if(flag){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}
	return 0;
}