In a graph G, if we can find a path from
node x to node y, we say that x can reach y. Now you are given a directed graph G with n
nodes and m edges. Besides, there are Q queries. Each query will contain two integers x and y. If x can reach y, print YES. Otherwise, print NO.
Note: We guarantee there is at most one
edge from node i to node j.
The first line will be an integer T (1
<= T <= 50). T is the number of test case.
For each test case, the first line will be
two integers n and m. (1 <= n <= 1000, 0 <= m <= min(n * n, 100000))
Then there will be m lines. Each line will
have two integers x, y. "x y" means there is an edge from x to y.
After that, there is an integer Q. (1 <=
Q <= 500) The following are Q lines. Each line will have two integers x, y.
All nodes are labeled from 1 to n.
For each query, if x can reach y, print YES. Otherwise, print NO.
For the first sample, 1 cannot reach 2, because 2 and 7 form a ring.
For the second sample, 2 can reach 7
For the third sample, 3 -> 5 -> 1
-> 6 is one path.