Palindromic Walk in Campus

A university campus can be represented as an undirected graph with n vertices and m edges. Each vertex (building) has a unique identifier and a label which is either 0 or 1. The label of each building is obtained by taking the building's unique number modulo 2. You are given this graph and then several queries. In each query you are given two vertices u and v. Your task is to decide whether there exists a walk (which is not necessarily a simple path, i.e. vertices and edges may be repeated) from u to v such that the sequence of labels along the walk forms a palindrome.

A string S is called a palindrome if it satisfies \[ S = S^R, \] that is, the string is the same when read forward and backward. For example, "010" and "1001" are palindromes, whereas "01" and "110" are not. Note that a string of length one is always a palindrome. In particular, if the query asks for a walk from a vertex to itself, then the answer is always YES (since the corresponding one-vertex walk forms a palindrome).

Important Observation: In any walk from u to v, the label at the start of the walk is f(u) and that at the end is f(v). For the label string to be a palindrome, we must have f(u) = f(v). Therefore, a necessary (and as it turns out, sufficient) condition for such a walk to exist (when u and v are distinct) is:

• f(u) = f(v) and
• u and v are in the same connected component of the graph.

Your task is to process multiple queries and output YES if such a palindromic walk exists, and NO otherwise.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10⁵), representing the number of vertices and edges respectively.

The second line is a binary string of length n consisting of characters '0' and '1'. The i-th character represents the label for vertex i (f(i) = the i-th character).

The next m lines each contain two integers u and v (1 ≤ u, v ≤ n), representing an undirected edge between vertices u and v.

The following line contains an integer q (1 ≤ q ≤ 10⁵), the number of queries.

Each of the next q lines contains two integers u and v specifying a query.

outputFormat

For each query, output a line containing YES if there exists a walk from vertex u to vertex v such that the sequence of labels along the walk forms a palindrome, or NO otherwise.

sample

3 2
010
1 2
2 3
3
1 1
1 3
1 2

YES
YES
NO