题意
https://www.luogu.org/problemnew/show/P5292
思考
最朴素的想法，从可行的二元组(u,v)向外拓展，及u的出边所指的颜色与v的出边所指的颜色若相同，继续更新二元组(u',v')，复杂度约为O(m)。
我们发现，很多时候边上的转移其实是没有必要的，因为有很多情况能转移到相同的字符串，因此我们要删去一些边，并且使得不改变原图的性质。
先考虑原图中边的两端颜色相同的边构成的连通块，若为二分图，则取其任意生成树；若不为二分图，则取其任意生成树，并添加一个自环。
二分图的意思，就是相同颜色段的长度只与奇偶性有关，当字符串另一端不断添加相同字符的同时，二分图中的字符可以不断地在A集合与B集合中转换。
两端颜色不同的边构成的连通块，也是取其任意生成树。
这样边数为O(n)级别，复杂度为O(n)。
代码
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int maxn=5E5+;
int head[maxn*],size,n,m,x,y,color[maxn],flag,q;
char c[maxn];
bool f[][],can[maxn];
struct edge{int from,to,next;};
struct pt{int x,y;};
queue<pt>Q;
struct graph
{
edge E[maxn*];
int head[maxn*],size;
void add(int u,int v)
{
E[++size].to=v;
E[size].next=head[u];
E[size].from=u;
head[u]=size;
}
}A,B,G;
void dfs1(int u,int now)
{
color[u]=now;
for(int i=A.head[u];i;i=A.E[i].next)
{
int v=A.E[i].to;
if(now==color[v])flag=;
if(color[v])continue;
G.add(u,v);
G.add(v,u);
if(now==)dfs1(v,);
else dfs1(v,);
}
}
void dfs2(int u)
{
color[u]=;
for(int i=B.head[u];i;i=B.E[i].next)
{
int v=B.E[i].to;
if(color[v])continue;
G.add(u,v);
G.add(v,u);
dfs2(v);
}
}
void init1()
{
for(int i=;i<=A.size;++i)
can[A.E[i].from]=can[A.E[i].to]=;
for(int u=;u<=n;++u)
{
if(color[u]||!can[u])continue;
flag=;
dfs1(u,);
if(flag)G.add(u,u);
}
}
void init2()
{
memset(color,,sizeof(color));
memset(can,,sizeof(can));
for(int i=;i<=B.size;++i)
can[B.E[i].from]=can[B.E[i].to]=;
for(int u=;u<=n;++u)
{
if(color[u]||!can[u])continue;
dfs2(u);
}
}
void work()
{
while(!Q.empty())
{
pt u=Q.front();
Q.pop();
for(int i=G.head[u.x];i;i=G.E[i].next)
{
for(int j=G.head[u.y];j;j=G.E[j].next)
{
int u=G.E[i].to,v=G.E[j].to;
if(c[u]==c[v])
{
if(!f[u][v])Q.push((pt){u,v});
f[u][v]=f[v][u]=;
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>q;
for(int i=;i<=n;++i)
{
cin>>c[i];
f[i][i]=;
Q.push((pt){i,i});
}
for(int i=;i<=m;++i)
{
cin>>x>>y;
if(c[x]==c[y])
{
A.add(x,y),A.add(y,x);
f[x][y]=f[y][x]=;
Q.push((pt){x,y});
}
else B.add(x,y),B.add(y,x);
}
init1();
init2();
work();
for(int i=;i<=q;++i)
{
cin>>x>>y;
if(f[x][y])cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return ;
}