Problem Background

HNOI2019 Day2T1

Problem Description

Each building in a school has a unique identification number. One day, feeling bored on campus, you decide to wander around aimlessly.

Having spent some time on campus, you are very familiar with the identification numbers of each building. You unconsciously note down the identification numbers of the surrounding buildings—but in reality, you don't really write them down. Instead, you mark each building with a 0 or 1 by taking the remainder of its identification number divided by 2. These marks, when concatenated, form a 01 string.

You are particularly interested in this string, especially when it is a palindrome. Thus, you decide to study this problem.

The school can be represented as a graph where buildings are vertices and there are undirected edges between certain vertices. Each vertex has a mark (0 or 1). You choose two vertices in the graph and want to know if there exists a path between these two vertices such that the marks of the vertices along the path form a palindrome.

A palindrome is a string that reads the same backward as forward, such as "010" and "1001", whereas "01" and "110" are not palindromes. Note that a string of length 1 is always a palindrome. Therefore, if the two vertices in the query are the same, such a path always exists. Additionally, the path does not necessarily have to be a simple path; that is, each edge and vertex can be traversed any number of times.

Input Format

The input file is named tour.in.

The first line contains three integers $n$, $m$, and $q$, representing the number of vertices, the number of edges, and the number of queries, respectively.

The second line is a 01 string of length $n$, where the $i$-th character represents the mark of the $i$-th vertex (vertex $i$), with vertices numbered starting from 1.

The next $m$ lines each contain two integers $u_i$ and $v_i$, indicating that there is an undirected edge between vertex $u_i$ and vertex $v_i$. There are no self-loops or duplicate edges.

The next $q$ lines each contain two integers $x_i$ and $y_i$, representing a query asking if there is a path between vertex $x_i$ and vertex $y_i$ that satisfies the conditions.

Output Format

The output file is named tour.out.

Output $q$ lines, each containing a string "YES" or "NO". Output "YES" if a path satisfying the conditions exists, and "NO" if it does not.

Sample Input and Output

Sample Input #1

5 4 2
00010
4 5
1 3
4 2
2 5
3 5
1 3

Sample Output #1

NO
YES

Sample Input #2

10 11 10
0011011111
4 6
10 6
5 9
4 7
10 7
5 8
1 9
5 7
1 10
5 1
5 6
10 3
7 4
8 10
9 4
8 9
6 6
2 2
9 9
10 9
3 4

Sample Output #2

NO
YES
YES
NO
YES
YES
YES
YES
YES
NO

Notes

Sample Explanation 1

For the first query, vertices 3 and 2 are not connected, so the answer is "NO".

For the second query, a valid path is 1→3, with the string formed by the marks being "00". Note that there are multiple valid paths.

Data Range

For 30% of the data, $1 \leq m \leq 10^4$;

For 70% of the data, $1 \leq n \leq 3000$, $1 \leq m \leq 5 \times 10^4$;

For 100% of the data, $1 \leq n \leq 5000$, $1 \leq m \leq 5 \times 10^5$, $1 \leq q \leq 10^5$.

Compilation Commands

For C++: g++ -o tour tour.cpp –lm -O2

For C: gcc -o tour tour.c –lm -O2

For Pascal: fpc tour.pas -O2

见题面 Input 部分

见题面 Output 部分