Message Reachability in Directed Networks

A network of devices is represented as a directed graph. Each device can send messages to other devices if there exists a directed path between them. Given n devices and m directed connections, your task is to answer q queries. In each query, you must determine whether a message can travel from a given source device to a target device through one or more connections.

Note: Every device is considered to be reachable from itself. The connectivity is defined in terms of directed paths; that is, the message can only travel in the direction of the connection.

The reachability condition can be expressed mathematically as follows:

\(\text{Let } G=(V,E) \text{ be a directed graph, where } V \text{ is the set of devices and } E \text{ is the set of directed edges. For any two vertices } u,v \in V, \text{ the device } v \text{ is reachable from } u \text{ if there exists a sequence } u = u_0, u_1, \dots, u_k = v \text{ such that } (u_i, u_{i+1}) \in E \text{ for } 0 \leq i

inputFormat

The input is given as follows:

1. The first line contains two integers n and m, where n is the number of devices and m is the number of directed connections.
2. The next m lines each contain two integers u and v which represent a directed edge from device u to device v.
3. The following line contains an integer q, the number of queries.
4. The next q lines each contain two integers representing the source and target devices for the query.

outputFormat

For each query, output a single line containing YES if the target device is reachable from the source device, or NO otherwise.

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

YES
YES
NO
NO