10751075 SUSTech Online Judge
Problem 1075 --Reachability Testing

## 1075: Reachability Testing

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2007  Solved: 334
[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.

[Submit][Status]