题面

题解

如果暴力的话，我们可以把所有的二元组全都扔进一个队列里，然后每次往两边更新同色点，这样的话复杂度是\(O(m^2)\)

怎么优化呢？

对于一个同色联通块，如果它是一个二分图，我们只要保留一棵生成树就够了。否则我们对其中任意一个点连一个自环

为什么呢？因为如果是二分图，重复走可以改变长度，但是无法改变长度的奇偶性。而如果不是二分图，那么是可以改变奇偶性的，我们需要连上一条自环来资瓷这种情况

对于不同的颜色，它们之间肯定是二分图，保留一棵生成树就可以了

这样的话可以把边数优化到\(O(n)\)，时间复杂度为\(O(n^2)\)

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}int read(char *s){    R int len=0;R char ch;while(((ch=getc())>'9'||ch<'0'));    for(s[++len]=ch;(ch=getc())>='0'&&ch<='9';s[++len]=ch);    return s[len+1]='\0',len;}const int N=5005,M=5e5+5;struct eg{int v,nx;}e[M<<1];int head[N],tot;inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}struct node{    int u,v;    node(){}    node(R int uu,R int vv):u(uu),v(vv){}};queue
      
       q;bool vis[N][N],flag;int col[N],fa[N];vector
       
        E[N];char s[N];int n,m,Q;int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}void dfs(int u,int c){    col[u]=c;    fp(i,0,E[u].size()-1){        int v=E[u][i];        if(s[u]!=s[v])continue;        if(col[u]==col[v])flag=0;        if(col[v])continue;        add(u,v),add(v,u),dfs(v,c^1);        vis[u][v]=vis[v][u]=1;        q.push(node(u,v));    }}int main(){//  freopen("testdata.in","r",stdin);    n=read(),m=read(),Q=read(),read(s);    fp(i,1,n)fa[i]=i;    for(R int i=1,u,v;i<=m;++i){        u=read(),v=read(),E[u].push_back(v),E[v].push_back(u);        if(s[u]!=s[v]&&find(u)!=find(v))add(u,v),add(v,u),fa[fa[v]]=fa[u];    }    fp(i,1,n)if(!col[i]){        flag=1,dfs(i,2);        if(!flag)add(i,i);     }    fp(i,1,n)vis[i][i]=1,q.push(node(i,i));    while(!q.empty()){        int x=q.front().u,y=q.front().v;q.pop();        for(int i=head[x],u=e[i].v;i;i=e[i].nx,u=e[i].v)            go(y)if(!vis[u][v]&&s[u]==s[v])                vis[u][v]=vis[v][u]=1,q.push(node(u,v));    }    for(R int u,v;Q;--Q)u=read(),v=read(),puts(vis[u][v]?"YES":"NO");    return 0;}