Valid Parentheses Path in a Graph

You are given an undirected graph with n nodes and m edges. Each node is labeled with a character which is either ( or ).

There are q queries. In each query, you are given two nodes x and y. Determine whether there exists a path (which is not necessarily simple – nodes and edges may be repeated) from node x to node y such that if you write down the characters on the visited nodes in order, the resulting string is a valid parentheses string.

A string S consisting of characters ( and ) is called a valid parentheses string if:

• The string is empty, or
• S = (T) for some valid parentheses string T, or
• S = T1T2 for some valid parentheses strings T1 and T2.

In other words, when reading the string from left to right, the number of ( characters minus the number of ) characters (the balance) never becomes negative, and the final balance is 0.

Note: The path can revisit nodes and edges arbitrarily.

The mathematical condition for a valid parentheses string can be expressed as follows. Let the string be represented as $s_1 s_2 \ldots s_k$, and define the balance after reading the first i characters as:

$$B(i) = \sum_{j=1}^{i} \begin{cases} 1, & \text{if } s_j = '(' \\ -1, & \text{if } s_j = ')' \end{cases} $$

Then, the string is valid if and only if:

$$B(i) \ge 0 \quad \text{for all } 1 \le i \le k \quad \text{and} \quad B(k)=0. $$

inputFormat

The first line contains two integers n and m — the number of nodes and edges in the graph.

The second line contains a string of length n. The i-th character is either ( or ), representing the label of node i.

The following m lines each contain two integers u and v indicating that there is an undirected edge between nodes u and v.

The next line contains an integer q, the number of queries.

Each of the following q lines contains two integers x and y — representing a query asking if there exists a path from node x to node y that forms a valid parentheses string.

outputFormat

For each query, print a single line containing Yes if there exists a path from x to y such that the parentheses string obtained by concatenating the labels of the nodes along that path is valid; otherwise, print No.

sample

3 2
())
1 2
2 3
2
1 2
1 3

Yes
No

</p>