P10572 [JRKSJ R8] +1-1

You are given an undirected graph with $n$ vertices and $m$ edges. Each vertex has a character `(` or `)` on it. There are $q$ queries. Each query gives $x, y$, and you need to determine whether there exists a path from $x$ to $y$ (it does not have to be a simple path) such that, if you write down the characters on the vertices along the path in order, the resulting string is a valid bracket sequence.

The first line contains three integers $n, m, q$. The second line contains a string of length $n$ consisting only of `(` and `)`, representing the characters on vertices $1 \dots n$. The next $m$ lines each contain two integers $u, v$, denoting an edge in the graph. The next $q$ lines each contain two integers $x, y$.

Output a 01 string of length $q$. The $i$-th character represents the answer to the $i$-th query: output `1` if such a path exists, otherwise output `0`.

Definition of a valid bracket sequence: * The empty string is a valid bracket sequence. * If $A, B$ are valid bracket sequences, then $AB$ is a valid bracket sequence. * If $A$ is a valid bracket sequence, then $(A)$ is a valid bracket sequence. * Any other string is not a valid bracket sequence. For example, `()` and `(()())` are valid bracket sequences, while `(()` and `())(` are not. ### Sample Explanation **To make it easier to read, there is a blank line between the edges and the queries in the sample input. However, this blank line does not exist in the actual testdata.**  Vertices $1, 2, 3$ have character `(`, and vertices $4, 5$ have character `)`. $1\to 2$: Obviously, a valid bracket sequence cannot end with `(`.\ $3\to 4$: The string represented by the path $3\to 4$ is `()`.\ $1\to 4$: The string represented by the path $1\to 3\to 2\to 4\to 5\to 4$ is `((()))`.\ $1\to 5$: The string represented by the path $1\to 2\to 4\to 5$ is `(())`.\ $2\to 5$: The string represented by the path $2\to 3\to 4\to 5$ is `(())`. ### Constraints This problem uses bundled testdata. - Subtask 1 (20 pts): $n, q \le 500$, $m \le 800$. - Subtask 2 (30 pts): The graph is a forest. - Subtask 3 (20 pts): $q \le 10$. - Subtask 4 (30 pts): No special restrictions. For all testdata, $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$. The given graph is guaranteed to have no multiple edges and no self-loops. Translated by ChatGPT 5