求助 WA#2

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=5*114514;
string s;
int n,m;
struct node{
	int u,v;
}edge[N];
vector<int> g[N],h[N];
int dfn[N],low[N],idx;
int stk[N],idx2;
int dcc_id;
int rot;
vector<int> dcc[N]; 
void dfs(int u){
//	cout<<u<<endl;
	dfn[u]=low[u]=++idx;
	stk[++idx2]=u;
	if(!g[u].size()&&u==rot){
		dcc[++dcc_id].push_back(u);
		return;
	}
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!dfn[v]){
			dfs(v);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
//				cout<<"tracy trick"<<endl;
				dcc_id++;
				int now=stk[idx2];
				do{
					dcc[dcc_id].push_back(now),idx2--,now=stk[idx2];
				}while(stk[idx2+1]!=v);
				dcc[dcc_id].push_back(u);
			}
		}
		else	low[u]=min(low[u],dfn[v]);
	}
}
void check(){
	cout<<dcc_id-n<<endl;
	for(int i=n+1;i<=dcc_id;i++){
		cout<<dcc[i].size()<<' ';
		for(int j=0;j<dcc[i].size();j++){
			int u=i,v=dcc[i][j];
			cout<<dcc[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<endl;
}
int fa[N][22];	//fa 倍增数组  
int dep[N];
void hadd(){
	for(int i=n+1;i<=dcc_id;i++){
		for(int j=0;j<dcc[i].size();j++){
			int u=i,v=dcc[i][j];
			h[u].push_back(v),h[v].push_back(u);
		}
	}
} 
void hdfs(int u){
	for(int i=0;i<h[u].size();i++){
		int v=h[u][i];
		if(fa[u][0]==v)	continue;
		fa[v][0]=u;
		for(int j=1;j<=20;j++)	fa[v][j]=fa[fa[v][j-1]][j-1];
		dep[v]=dep[u]+1;
		hdfs(v); 
	}
}
int LCA(int u,int v){
	if(dep[u]<dep[v])	swap(u,v);
	for(int i=20;i>=0;i--){
		if(dep[fa[u][i]]>=dep[v])	u=fa[u][i];
	} 
	if(u==v)	return u;
	for(int i=20;i>=0;i--){
		if(fa[u][i]!=fa[v][i])	u=fa[u][i],v=fa[v][i];
	}
	return fa[u][0];
}
void solve(){
	cin>>n>>m;
	cin>>s;
	dcc_id=n;
	idx=0,idx2=0;
	s=' '+s;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		u++,v++;	//克服原先下标不统一的问题  
		edge[i]=(node){u,v};
		if(s[u]!=s[v])	g[u].push_back(v),g[v].push_back(u);
	}
//	cout<<"谭总的世界-031"<<endl;
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			rot=i;
			dfs(i);
			h[i].push_back(0),h[0].push_back(i);
		}	
	}
//	check();
	hadd(),dep[0]=0,hdfs(0); 
	int include13=0;
	for(int i=1;i<=m;i++){
		int u=edge[i].u,v=edge[i].v;
		if(s[u]==s[v]){
			if(LCA(u,v)==u||LCA(u,v)==v)	include13=1;
		} 
	}
	cout<<(include13?"yes":"no")<<endl;
	for(int i=0;i<=dcc_id;i++){
		g[i].clear(),h[i].clear(),dcc[i].clear();
		dfn[i]=low[i]=stk[i]=0;
		for(int j=0;j<=20;j++)	fa[i][j]=0;
		dep[i]=0;
	}
}
int T;
signed main(){
	cin>>T;
	while(T--)	solve();
	return 0;
}