Allen's Graph


Submit solution

Points: 7
Time limit: 2.0s
Java 3.0s
Memory limit: 128M

Author:
Problem type

For his homework, allentao 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.

allentao, 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

There are no comments at the moment.