Allen's Graph
For his homework,
is required to solve the following problem:Given a graph consisting of \(N\) nodes and \(M\) directed edges, for each of \(Q\) queries, each with two nodes \(u\) and \(v\), report whether or not it is possible to travel from \(u\) to \(v\) while always remaining on an edge.
, finding the problem easy, gives it to you instead for ICS preparation.
Can you solve it?
Input Specification
On the first line, there will be two space separated integers \(N\) and \(M\), the number of nodes and edges in the graph, respectively.
On each of the following \(M\) lines, there will be two space separated integers, \(a\) and \(b\), denoting a directed edge between \(a\) and \(b\).
On the next line, there will be an integer \(Q\), the number of queries.
On each of the following \(Q\) lines, there will be two space separated integers, \(u\) and \(v\), describing the query.
Output Specification
Output \(Q\) lines, each line consisting of either YES
, indicating that the travel described above is possible, or NO
, indicating that the travel described above is impossible.
Constraints
\(1 \le N \le 10^4\)
\(1 \le M \le \frac{N(N-1)}{2}\)
\(1 \le Q \le 10^3\)
\(1 \le a, b, u, v \le N\)
Sample Input
3 2
1 2
2 3
2
1 2
2 1
Sample Output
YES
NO
Comments