{"raw_statement":[{"iden":"statement","content":"给你 $n$ 个点 $m$ 条边的无向图，每个结点上有一个字符 `(` 或者 `)`。\n\n有 $q$ 次查询，每次查询给出 $x,y$，你需要判断是否存在一条从 $x$ 到 $y$ 的路径（不需要保证是简单路径）满足将路径上的点上的字符顺次写下来得到的字符串是合法括号串。"},{"iden":"input","content":"第一行三个整数 $n,m,q$。\n\n第二行一个只包含 `(` 和 `)` 的长度为 $n$ 的字符串表示结点 $1\\dots n$ 上的字符。\n\n下面 $m$ 行，每行两个整数 $u,v$ 表示图上的一条边。\n\n下面 $q$ 行，每行两个整数 $x,y$。"},{"iden":"output","content":"一个长度为 $q$ 的 01 串，第 $i$ 个字符表示第 $i$ 次询问的答案，1 表示存在这样的路径，0 表示不存在这样的路径。"},{"iden":"note","content":"合法括号串的定义：\n\n* 空字符串是合法括号串\n* 若 $A,B$ 是合法括号串，则 $AB$ 是合法括号串\n* 若 $A$ 是合法括号串，则 $(A)$ 是合法括号串\n* 除此之外的其他字符串均不是合法括号串\n\n如 `()`、`(()())` 是合法括号串，`(()`、`())(` 不是合法括号串。\n\n### 样例解释\n\n**为了方便观察，输入的边和询问之间有一个换行。但数据中并不存在这个换行。**\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/x2lp3c7m.png)\n\n其中 $1,2,3$ 号点的字符是 `(`，$4,5$ 号点的字符是 `)`。\n\n$1\\to 2$：显然，合法括号串不可能以 `(` 结尾。\\\n$3\\to 4$：路径 $3\\to 4$ 表示的字符串是 `()`。\\\n$1\\to 4$：路径 $1\\to 3\\to 2\\to 4\\to 5\\to 4$ 表示的字符串是 `((()))`。\\\n$1\\to 5$：路径 $1\\to 2\\to 4\\to 5$ 表示的字符串是 `(())`。\\\n$2\\to 5$：路径 $2\\to 3\\to 4\\to 5$ 表示的字符串是 `(())`。\n\n### 数据规模与约定\n\n本题采用捆绑测试。\n\n- Subtask 1（20 pts）：$n,q\\leq 500$，$m \\leq 800$；\n- Subtask 2（30 pts）：图是森林；\n- Subtask 3（20 pts）：$q\\le 10$；\n- Subtask 4（30 pts）：无特殊限制。\n\n对于所有数据，满足 $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$，保证给出的图无重边、无自环。"}],"translated_statement":null,"sample_group":[["5 6 5\n((())\n1 2\n1 3\n2 3\n3 4\n4 5\n2 4\n\n1 2\n3 4\n1 4\n1 5\n2 5\n","01111"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}