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 query, you are allowed to remove at most one vertex from the graph (you may choose not to remove any vertex, or remove exactly one). The removed vertex can be any vertex in the graph. After the removal, 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 three integer ~a~, ~b~ and ~r~ which represented the removed vertex.

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 3
2 1
3 1
3 2
4 3
1 4 2
1 4 3
2 3 3

Example Output

Y
N 
N