CSES - Reachability Queries
  • Time limit: 1.00 s
  • Memory limit: 512 MB

A directed graph consists of nn nodes and mm edges. The edges are numbered 1,2,,n1,2,\dots,n.

Your task is to answer qq queries of the form "can you reach node bb from node aa?"

Input

The first input line has three integers nn, mm and qq: the number of nodes, edges and queries.

Then there are mm lines describing the edges. Each line has two distinct integers aa and bb: there is an edge from node aa to node bb.

Finally there are qq lines describing the queries. Each line consists of two integers aa and bb: "can you reach node bb from node aa?"

Output

Print the answer for each query: either "YES" or "NO".

Constraints

  • 1n51041 \le n \le 5 \cdot 10^4
  • 1m,q1051 \le m,q \le 10^5

Example

Input:

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

Output:

YES
NO
YES