点和点之间关系密切。考虑刷表然后O(1)回答
暴力：
f[i][j]i到j是否有回文路径，暴力枚举出边。O(m^2)（每个边的对儿会恰好被枚举4次）
优化：
题目只要求“可行性”。考虑在不改变可行性情况下减少边数
提出来所有两边标号相同的边
对于1和0的连通块，如果连通块是二分图，只保留生成树即可（因为连通块内，a到b经过的边的奇偶性确定，至于可能路途遥远一些，但是可以让对称的那一半重复往返走一条边）
如果不是，那么a到b的奇偶性可以是奇数可以是偶数，随便连一个自环即可。
提出来所有两边标号不同的边
这个图显然是二分图
对于这个二分图，保留一个生成树即可
同理也可以在对称的位置来回走
对于二分图：
1.连通块染色
2.带权并查集
（自环连一个就好了，否则还是会TLE）
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar(' ');} namespace Miracle{ const int N=5005; const int M=500000+5; int n,m,q; struct node{ int nxt,to; }e[2*M+2*N]; int hd[N],cnt; char s[N]; int co[N]; void add(int x,int y){ // if(x<y) cout<<" add "<<x<<" and "<<y<<endl; e[++cnt].nxt=hd[x]; e[cnt].to=y; hd[x]=cnt; } int ex[M],ey[M]; int gf[N]; int fin(int x){ return gf[x]==x?x:gf[x]=fin(gf[x]); } int fa[N]; int papa(int x){ return fa[x]==x?x:fa[x]=papa(fa[x]); } int c[N]; int num,rt[N]; int ji[N]; void dfs(int x,int se){ c[x]=se; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(co[y]!=co[x]) continue; if(c[y]){ if(c[y]==c[x]){ ji[num]=1; } }else{ dfs(y,3-se); } } } void build(){ for(reg i=1;i<=n;++i){ if(c[i]==0){ ++num;rt[num]=i; dfs(i,2); } } memset(hd,0,sizeof hd);cnt=0; for(reg i=1;i<=m;++i){ if(co[ex[i]]==co[ey[i]]){ int k1=fin(ex[i]),k2=fin(ey[i]); if(k1!=k2){ gf[k1]=k2; add(ex[i],ey[i]); add(ey[i],ex[i]); } }else{ int k1=papa(ex[i]),k2=papa(ey[i]); if(k1!=k2){ fa[k1]=k2; add(ex[i],ey[i]); add(ey[i],ex[i]); } } } for(reg i=1;i<=num;++i){ if(ji[i]){ add(rt[i],rt[i]); } } } bool f[N][N]; queue<pii>qs; void bfs(){ for(reg i=1;i<=n;++i){ f[i][i]=1;qs.push(mk(i,i)); } for(reg i=1;i<=m;++i){ if(co[ex[i]]==co[ey[i]]){ f[ex[i]][ey[i]]=1; f[ey[i]][ex[i]]=1; qs.push(mk(ex[i],ey[i])); } } while(!qs.empty()){ pii now=qs.front();qs.pop(); int x=now.fi,y=now.se; // cout<<" bfs "<<x<<" "<<y<<endl; for(reg i=hd[x];i;i=e[i].nxt){ int t1=e[i].to; for(reg j=hd[y];j;j=e[j].nxt){ int t2=e[j].to; if(co[t1]==co[t2]&&!f[t1][t2]){ f[t1][t2]=f[t2][t1]=1; qs.push(mk(t1,t2)); } } } } } int main(){ rd(n);rd(m);rd(q); scanf("%s",s+1); for(reg i=1;i<=n;++i) co[i]=s[i]-'0'; int x,y; for(reg i=1;i<=m;++i){ rd(x);rd(y); ex[i]=x;ey[i]=y; add(x,y);add(y,x); } for(reg i=1;i<=n;++i){ gf[i]=i;fa[i]=i; } build(); // cout<<" cnt "<<cnt<<endl; bfs(); while(q--){ rd(x);rd(y); puts(f[x][y]?"YES":"NO"); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */