提交记录：161613588

思路大概如下：

尝试从 $x$ 走到两个端点都是 ( 的边（记为L型边）反复横跳，再走到一个奇环绕 1 或 2 圈，再走到两个端点都是 ) 的边（记为R型边）反复横跳，然后到 $y$。

如果中间没有奇环，则是二分图，要求 $x$ 和 $y$ 不在二分图的同一部。

如果不能到达L型或R型边，则是L型边和R型边交替。

• bfs1： 建连通块1，防止 $x$ 到不了 $y$。

• bfs2： L型边和R型边交替形成的连通块2。

• bfs3： 二分图染色找奇环，odd[i] 表示第 $i$ 个连通块1里面有奇环，否则 col[i] 标记点 i 在二分图的哪一部。

• bfs4： 从L型边或R型边出发，找哪些(的点能到L型边，哪些)的点能到R型边。okl[i] 表示在 i 点之前至少要经过 okl[i] 个(的点，才能从 i 走到L型边，okr[i] 类似，用的是 dijkstra。

代码：

#include<bits/stdc++.h>
#define Maxn 500005
using namespace std;
int n,m,t;
char a[Maxn];
vector<int> e[Maxn];

int vis[Maxn],visl[Maxn],visr[Maxn];
queue<int> q;
priority_queue<pair<int,int> > ql,qr;

int scc1[Maxn],tot1;
void bfs1(int x){
	while(!q.empty()){ q.pop(); }
	scc1[x] = ++tot1;
	q.emplace(x); vis[x]=1;
	while(!q.empty()){
		x = q.front(); q.pop();
		for(int y : e[x])if(!vis[y]){
			scc1[y] = tot1;
			q.emplace(y); vis[y]=1;
		}
	}
}

int scc2[Maxn],tot2;
void bfs2(int x){
	while(!q.empty()){ q.pop(); }
	scc2[x] = ++tot2;
	q.emplace(x); vis[x]=1;
	while(!q.empty()){
		x = q.front(); q.pop();
		for(int y : e[x])if(!vis[y] && a[x] != a[y]){
			scc2[y] = tot2;
			q.emplace(y); vis[y]=1;
		}
	}
}

int col[Maxn],odd[Maxn];
void bfs3(int x){
	while(!q.empty()){ q.pop(); }
	col[x] = 0; q.emplace(x);
	while(!q.empty()){
		x = q.front(); q.pop();
		for(int y : e[x]){
			if(~col[y]){
				if(col[y] == col[x]){
					odd[scc1[x]] = 1; return;
				}
			} else {
				col[y] = col[x] ^ 1; q.emplace(y);
			}
		}
	}
}

int okl[Maxn],okr[Maxn];
void bfs4(int x){
	while(!q.empty()){ q.pop(); }
	q.emplace(x); vis[x]=1;
	while(!q.empty()){
		x = q.front(); q.pop();
		for(int y : e[x])if(!vis[y]){
			q.emplace(y); vis[y]=1;
			if(a[x] != a[y]){ continue; }
			if(a[x] == '('){
				okl[x] = okl[y] = 0;
				ql.emplace(0, x); ql.emplace(0, y);
			} else {
				okr[x] = okr[y] = 0;
				qr.emplace(0, x); qr.emplace(0, y);
			}
		}
	}
}
void dij(){
	int x,z;
	while(!ql.empty()){
		x = ql.top().second; ql.pop();
		if(visl[x]){ continue; }
		visl[x] = 1;
		for(int y : e[x]){
			z = max(0, okl[x] + ((a[y] == ')') ? 1 : -1));
			if(okl[y] > z){
				okl[y] = z; ql.emplace(-z, y);
			}
		}
	}
	while(!qr.empty()){
		x = qr.top().second; qr.pop();
		if(visr[x]){ continue; }
		visr[x] = 1;
		for(int y : e[x]){
			z = max(0, okr[x] + ((a[y] == '(') ? 1 : -1));
			if(okr[y] > z){
				okr[y] = z; qr.emplace(-z, y);
			}
		}
	}
}

int main(){
	scanf("%d%d%d%s",&n,&m,&t,a+1);
	int x,y,z;
	for(int i=1; i<=m; i++){
		scanf("%d%d",&x,&y);
		e[x].emplace_back(y);
		e[y].emplace_back(x);
	}
	
	for(int i=1; i<=n; i++)if(!vis[i]){
		bfs1(i);
	}
	
	memset(col, 0xff, sizeof(col));
	for(int i=1; i<=n; i++)if(col[i] == -1){
		bfs3(i);
	}
	
	memset(vis, 0, sizeof(vis));
	for(int i=1; i<=n; i++)if(!vis[i]){
		bfs2(i);
	}
	
	memset(vis, 0, sizeof(vis));
	memset(okl, 0x3f, sizeof(okl));
	memset(okr, 0x3f, sizeof(okr));
	for(int i=1; i<=n; i++)if(!vis[i]){
		bfs4(i);
		dij();
	}
	
	while(t--){
		scanf("%d%d",&x,&y);
		if(scc1[x] != scc1[y]){
			printf("0"); continue;
		}
		z = scc1[x];
		if(okl[x] || okr[y]){
			if(a[x]=='(' && a[y]==')' && scc2[x] == scc2[y]){
				printf("1");
			} else {
				printf("0");
			}
			continue;
		}
		if(odd[z] || col[x] != col[y]){
			printf("1");
		} else {
			printf("0");
		}
	}
	return 0;
}

Subtask #4 的三个点 WA 了，“read 0, expected 1”。