10751075 SUSTech Online Judge
Problem 1075 --Reachability Testing

1075: Reachability Testing

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2008  Solved: 335
[Submit][Status][Web Board]

Description

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. 

Input

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. 

Output

For each query, if x can reach y, print YES. Otherwise, print NO.

Sample Input

1
7 7
1 6
6 4
4 3
3 5
5 1
2 7
7 2
6
1 2
2 7
7 2
3 6
4 6
5 4

Sample Output

NO
YES
YES
YES
YES
YES

HINT


For the first sample, 1 cannot reach 2, because 2 and 7 form a ring.



For the second sample, 2 can reach 7
directly.



For the third sample, 3 -> 5 -> 1
-> 6 is one path. 

Source

[Submit][Status]