Given an udirected graph which contains n vertices (indexed from 0) and m edges. Given q queries and each queries contains two integers a and b. For each queries, determine if the edge between a and b is a bridge

Input

The first line contains three integers n, m, q (n, m ≤ 10^5, q ≤ 200)

Each line in the next m lines contains two integers u and v which is an edge between u and v

Each line in the next q lines contains two integers a and b (0 ≤ a, b < n).

Output

For each query, output "Y" if the given edge is a bridge, otherwise output "N" (without the quote) in a single line.

Example

Input

4 4 2
0 1
1 2
2 0
2 3
3 2
0 1

Output

Y
N