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 \le 10^4, m, q \le 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

• For each query, output in one line "Y" if there is a path from a to b, otherwise output "N"

Example Input

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

Example Output

Y
N