1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
char s[MAXN];
int n, m, q;
vector<int> G0[MAXN], G1[MAXN], G[MAXN];
bool vis0[MAXN], vis1[MAXN];
bool vis2[MAXN], vis3[MAXN];
bool col[MAXN];
bool flag;
queue<pair<int, int> > qu;
bool vis[MAXN][MAXN], f[MAXN][MAXN];
void dfs_ck0(int u) {
vis1[u] = 1;
for (auto v : G0[u]) {
if (vis1[v] == 0) {
col[v] = col[u] ^ 1;
dfs_ck0(v);
} else if (col[v] == col[u]) flag = 0;
}
}
void dfs_gen0(int u) {
vis0[u] = 1;
for (auto v : G0[u])
if (vis0[v] == 0)
G[u].push_back(v), G[v].push_back(u), dfs_gen0(v);
}
void dfs_ck1(int u) {
vis3[u] = 1;
for (auto v : G1[u]) {
if (vis3[v] == 0) {
col[v] = col[u] ^ 1;
dfs_ck1(v);
} else if (col[v] == col[u]) flag = 0;
}
}
void dfs_gen1(int u) {
vis2[u] = 1;
for (auto v : G1[u])
if (vis2[v] == 0)
G[u].push_back(v), G[v].push_back(u), dfs_gen1(v);
}
int main() {
scanf("%d%d%d", &n, &m, &q);
scanf("%s", s + 1);
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
if (s[u] == s[v])
G0[u].push_back(v), G0[v].push_back(u);
else
G1[u].push_back(v), G1[v].push_back(u);
}
for (int i = 1; i <= n; ++i) {
if (vis0[i]) continue;
flag = 1;
dfs_ck0(i);
dfs_gen0(i);
if (flag == 0) G[i].push_back(i);
}
memset(col, 0, sizeof(col));
for (int i = 1; i <= n; ++i) {
if (vis2[i]) continue;
flag = 1;
dfs_ck1(i);
dfs_gen1(i);
if (flag == 0) G[i].push_back(i);
}
for (int i = 1; i <= n; ++i) {
qu.push(make_pair(i, i));
vis[i][i] = 1;
}
for (int u = 1; u <= n; ++u) {
for (auto v : G[u]) {
if (s[u] == s[v])
qu.push(make_pair(u, v)), vis[u][v] = vis[v][u] = 1;
}
}
while (qu.size()) {
int x = qu.front().first, y = qu.front().second;
qu.pop();
f[x][y] = f[y][x] = 1;
for (auto z : G[x]) {
for (auto w : G[y]) {
if (s[z] == s[w] && vis[z][w] == 0)
qu.push(make_pair(z, w)), vis[z][w] = vis[w][z] = 1;
}
}
}
for (int i = 1; i <= q; ++i) {
int a, b;
scanf("%d%d", &a, &b);
if (f[a][b]) puts("YES");
else puts("NO");
}
return 0;
}
|