30分 TLE 求条

#include<bits/stdc++.h>
using namespace std;
char col[5005];
int n , m , Q , po;
queue<pair<int , int> > q;
vector<int> vec[5005] , same[5005] , diff[5005];
int color[5005] , dp[5005][5005] , dep[5005] , vis[5005];
void fac(int x , int y){
    if(dp[x][y]) return ;
    dp[x][y] = 1;
    q.push({x , y});
}
void dfs1(int x , int p){
    dep[x] = dep[p] + 1;
    vis[x] = 1;
    for(auto i : diff[x]){
    	if(vis[i] == 0){
    		vec[x].push_back(i);
    		vec[i].push_back(x);
    		dfs1(i , x);
    	}
    	else if(po && (dep[x] - dep[i]) % 2 == 0){
    		vec[x].push_back(i);
    		vec[i].push_back(x);	
    	}
    }
}
void dfs2(int x , int p){
    dep[x] = dep[p] + 1;
    vis[x] = 1;
    for(auto i : same[x]){
    	if(vis[i] == 0){
    		vec[x].push_back(i);
    		vec[i].push_back(x);
    		dfs2(i , x);
    	}
    	else if(po && (dep[x] - dep[i]) % 2 == 0){
    		vec[x].push_back(i);
    		vec[i].push_back(x);	
    	}
    }
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	cin >> n >> m >> Q >> (col + 1);
    while(m--){
        int x , y;
		cin >> x >> y;
        if(col[x] == col[y]){
            same[x].push_back(y);
            same[y].push_back(x);
            fac(x , y) , fac(y , x);
        }
        else{
            diff[x].push_back(y);
            diff[y].push_back(x);
        }
    }
    memset(dep , 0 , sizeof dep);
    memset(vis , 0 , sizeof vis);
    for(int i = 1 ; i <= n ; i++){
        if(vis[i] == 0){
            po = 1;
            dfs1(i , 0);
        }
    }
    
    memset(dep , 0 , sizeof dep);
    memset(vis , 0 , sizeof vis);
    for(int i = 1 ; i <= n ; i++){
        if(vis[i] == 0){
            po = 1;
            dfs2(i , 0);
        }
    }
    for(int i = 1 ; i <= n ; i++) fac(i , i);
    while(!q.empty()){
        int x = q.front().first , y = q.front().second;
        q.pop();
        for(int i = 0 ; i < vec[x].size() ; i++){
            for(int j = 0 ; j < vec[y].size() ; j++){
                if(col[vec[x][i]] == col[vec[y][j]]) fac(vec[x][i] , vec[y][j]);
            }
        }
    }
    while(Q--){
        int x , y;
		cin >> x >> y;
        if(dp[x][y]) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}