我的思路是两端和路径颜色相同的话能连就连。

然后暴力枚举剩余的点找到一种情况，看是否成立。

AC 75 WA 2 自闭麻了。

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

typedef long long ll;
typedef pair<int,char> pii;
const int N=1e6+3,M=4e6+3;
int n,m,X[N],Y[N],f[N];
char col[N];
bool v[N],vis[N];
struct Nod{int x,id;char ch;};
vector<Nod>ve[N];
queue<int>q;
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
int main()
{
	cin>>n>>m;char z;int cnt=0;
	for(int i=1,x,y;i<=m;i++)
	{
	    cin>>x>>y>>z;X[i]=x;Y[i]=y; 
		ve[x].push_back({y,i,z});
		ve[y].push_back({x,i,z}); 
	}
	for(int i=1;i<=n;i++)cin>>col[i],f[i]=i;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<ve[i].size();j++)
		{
			int x=ve[i][j].x;z=ve[i][j].ch;
			if(col[i]==z&&col[x]==z&&F(i)!=F(x)&&!vis[ve[i][j].id])
			{
			    f[F(x)]=F(i),vis[ve[i][j].id]=1,cnt++;
			    v[i]=v[x]=1;
			}
		}
	}
	int tot=cnt,zz=0;
	if(!cnt){cout<<"No";return 0;}
	for(int i=1;i<=n;i++)if(!v[i])
	{
		int fl=0;
		for(int j=0;j<ve[i].size();j++)
		{
			int x=ve[i][j].x;
			if(ve[i][j].ch==col[i]&&F(i)!=F(x)&&!vis[ve[i][j].id])
			{
				v[i]=1;f[F(x)]=F(i);vis[ve[i][j].id]=1;break;
			}
		}
		if(!v[i]){cout<<"No";return 0;}
	}
	int res=0;
	for(int i=1;i<=m;i++)if(vis[i])res++;
	for(int i=1;i<=m;i++)if(F(X[i])!=F(Y[i]))vis[i]=1,res++,f[F(X[i])]=F(Y[i]);
	if(res!=n-1){cout<<"No";return 0;}
	cout<<"Yes"<<endl;
	for(int i=1;i<=m;i++)if(vis[i])cout<<i<<" "; 
}