Palindrome Path

Points: 20 (partial)

Time limit: 2.0s

Memory limit: 512M

Problem types

Andrew and William are playing a game on an undirected graph with $N$ ~N~ vertices, numbered from 1 to $N$ ~N~. Each vertex has a binary label, either 0 or 1. During the game, Andrew selects two vertices $u$ ~u~ and $v$ ~v~ ( $1 \leq u, v \leq N$ ~1 \leq u, v \leq N~), and asks William if there exists a palindrome path from $u$ ~u~ to $v$ ~v~. A palindrome path is defined as a path where the sequence of vertex labels recorded from $u$ ~u~ to $v$ ~v~ forms a palindrome. The path does not have to be a simple path; William can visit the same vertex multiple times.

Write a program to help William determine if such a palindrome path exists for each query.

Input Specification

The first line includes three integers, $N$ ~N~, $M$ ~M~ and $Q$ ~Q~ ( $N \le 5\,000, M\le 500\,000, Q\le 100\,000$ ), the number of vertices, the number of edges and the number of queries made by Andrew.

The second line includes a binary string with length $N$ ~N~, where the $i^{th}$ ~i^{th}~ character is the label of vertex $i$ ~i~.

Each of the following $M$ ~M~ lines includes two integers, $u$ ~u~ and $v$ ~v~, an edge between $u$ ~u~ and $v$ ~v~.

Each of the following $Q$ ~Q~ lines includes two integers, $u$ ~u~ and $v$ ~v~, a query to ask if there exists a palindrome path from $u$ ~u~ to $v$ ~v~.

Output Specification

For each query, print out YES if there exists a palindrome path, otherwise NO.

Constraints

Subtask	Points	Additional constraints
$1$ ~1~	$30$ ~30~	$M \le 10\,000$ ~M \le 10\,000~
$2$ ~2~	$40$ ~40~	$N \le 3\,000$ ~N \le 3\,000~, $M \le 50\,000$ ~M \le 50\,000~
$3$ ~3~	$30$ ~30~	No additional constraints

Sample Input

Sample Output

NO
YES

Comments

There are no comments at the moment.