EIU Programming Practices and Exams

Given a directed graph includes n vertices (from 1 to n) and m edges. Given q queries of two integers a and b. For each queries, check if there is a path from a to b which visite at most one intermediate vertex.

Input

The first line contains three integers n, m and q(n <=10^4, m, q<=10^5)

Each line in the next m lines contains two integer u and v which represented an edge from v to u.

Each line in the next m lines contains two integer a and b.

Output

Với mỗi truy vấn, xuất ra trên 1 dòng "Y" nếu có đường đi từ a đến b, ngược lại xuất ra "N"

For each query, output in one line  "U" if there is a path from a to b, otherwise output "N" (without the quotes)

Example

Input:
4 4 2
1 2
1 3
2 3
3 1
1 2
1 4
Output: 
Y
N