题目描述

给你 $n$ 个点 $m$ 条边的无向图，每个结点上有一个字符 ( 或者 )。

有 $q$ 次查询，每次查询给出 $x,y$，你需要判断是否存在一条从 $x$ 到 $y$ 的路径（不需要保证是简单路径）满足将路径上的点上的字符顺次写下来得到的字符串是合法括号串。

输入格式

第一行三个整数 $n,m,q$。

第二行一个只包含 ( 和 ) 的长度为 $n$ 的字符串表示结点 $1\dots n$ 上的字符。

下面 $m$ 行，每行两个整数 $u,v$ 表示图上的一条边。

下面 $q$ 行，每行两个整数 $x,y$。

输出格式

一个长度为 $q$ 的 01 串，第 $i$ 个字符表示第 $i$ 次询问的答案，1 表示存在这样的路径，0 表示不存在这样的路径。

5 6 5
((())
1 2
1 3
2 3
3 4
4 5
2 4

1 2
3 4
1 4
1 5
2 5

01111

提示

合法括号串的定义：

• 空字符串是合法括号串
• 若 $A,B$ 是合法括号串，则 $AB$ 是合法括号串
• 若 $A$ 是合法括号串，则 $(A)$ 是合法括号串
• 除此之外的其他字符串均不是合法括号串

如 ()、(()()) 是合法括号串，(()、())( 不是合法括号串。

样例解释

为了方便观察，输入的边和询问之间有一个换行。但数据中并不存在这个换行。

其中 $1,2,3$ 号点的字符是 (，$4,5$ 号点的字符是 )。

$1\to 2$：显然，合法括号串不可能以 ( 结尾。
$3\to 4$：路径 $3\to 4$ 表示的字符串是 ()。
$1\to 4$：路径 $1\to 3\to 2\to 4\to 5\to 4$ 表示的字符串是 ((()))。
$1\to 5$：路径 $1\to 2\to 4\to 5$ 表示的字符串是 (())。
$2\to 5$：路径 $2\to 3\to 4\to 5$ 表示的字符串是 (())。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（20 pts）：$n,q\leq 500$，$m \leq 800$；
• Subtask 2（30 pts）：图是森林；
• Subtask 3（20 pts）：$q\le 10$；
• Subtask 4（30 pts）：无特殊限制。

对于所有数据，满足 $1\le n,q\le 5\times 10^5$，$0\le m\le \min(\frac{n\times(n-1)}{2},5\times 10^5)$，$1\le u,v,x,y\le n$，保证给出的图无重边、无自环。