Problem Description

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.

Input Format

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 Format

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.

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

Hint

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