Palindrome Path

View as PDF

Submit solution

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 vertices, numbered from 1 to N. Each vertex has a binary label, either 0 or 1. During the game, Andrew selects two vertices u and v (1 \leq u, v \leq N), and asks William if there exists a palindrome path from u to v. A palindrome path is defined as a path where the sequence of vertex labels recorded from u to 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, M and 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, where the i^{th} character is the label of vertex i.

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

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

Output Specification

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


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

Sample Input

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

Sample Output



There are no comments at the moment.