K. Bad Friend
time limit per test
2 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

In an imaginary country called IM, there are $$$n$$$ cities and $$$m$$$ directed roads. However, these roads may not connect all the cities.

$$$\textit{Kifah}$$$ has been a resident of IM for many years and knows the country well. On a sunny morning, while chatting with his friend $$$\textit{Abdullah}$$$, a claim was made. $$$\textit{Abdullah}$$$ stated that he had moved to IM but was unsure of his exact location. Skeptical, $$$\textit{Kifah}$$$ didn't believe him and demanded proof. In response, $$$\textit{Abdullah}$$$ provided a set of city pairs, asserting that for each pair, there exists a path starting from the first city and ending at the second, passing through $$$\textit{Abdullah's}$$$ current city.

Can you help $$$\textit{Kifah}$$$ to check if there is any contradiction in $$$\textit{Abdullah's}$$$ claims.

In this Problem you will be given a graph consists of $$$n$$$ nodes and $$$m$$$ directed edges. Note that the graph may not be connected, but it is guaranteed that there is no multi-edges or self-loops.

Then you will be given a set of $$$q$$$ pairs of nodes $$$(a, b)$$$ that claims: there is a path starts from $$$a$$$, ends at $$$b$$$ and passes by the city where $$$\textit{Abdullah}$$$ is. These paths may traverse nodes or roads multiple times.

Your goal is to help $$$\textit{Kifah}$$$ determine whether $$$\textit{Abdullah's}$$$ claims hold without contradiction, thus verifying his honesty.

Input

The first line contains a single integer $$$Tc$$$ $$$(1 \le Tc \le 5 \cdot 10^4)$$$ — the number of test cases.

The first line of each test case contains two integers $$$n, m$$$ $$$(1 \le n \le 5 \cdot 10^4,$$$ $$$1 \le m \le min(n \cdot (n-1), 10^5))$$$ — the number of vertices and edges in the graph respectively.

For the following $$$m$$$ lines, each line contains two integers $$$(u, v)$$$ $$$(1 \le u,$$$ v $$$\le n)$$$, describing a directed edge from vertex $$$u$$$ to vertex $$$v$$$. It is guaranteed that there are no multi-edges or self-loops in the graph.

The next line contains a single integer $$$q$$$ $$$(1 \le q \le 5 \cdot 10^4)$$$, the number of pairs $$$\textit{Abdullah}$$$ provided.

For the following $$$q$$$ lines, each line contains two integers $$$(a, b)$$$ $$$(1 \le a,$$$ b $$$\le n)$$$, describing a claim that says: There is a path starts from $$$a$$$, ends at $$$b$$$ and pass by the city where $$$\textit{Abdullah}$$$ is. These paths may traverse nodes or roads multiple times.

It is guaranteed that both the sum of $$$n$$$ and $$$q$$$ over all test cases doesn't exceed $$$5 \cdot 10^4$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

For each test case, output "YES" (without quotes) if $$$\textit{Kifah}$$$ can't find any contradiction in $$$\textit{Abdullah's}$$$ claims, and "NO" (without quotes) otherwise.

Example
Input
2
4 3
1 2
2 3
3 4
2
1 3
2 4
5 4
1 2
2 3
4 3
5 3
2
1 3
5 4
Output
YES
NO
Note

In the first testcase, both nodes $$$2$$$ and $$$3$$$ meet the claims. For node $$$2$$$ the path $$$1 \rightarrow 2 \rightarrow 3$$$ meets the first pair $$$(1, 3)$$$, and the path $$$2 \rightarrow 3 \rightarrow 4$$$ meets the second pair $$$(2, 4)$$$. So we can't say that $$$\textit{Abdullah}$$$ is a Liar, that's why we provide "YES".

In the second testcase, there is no node that meets the constraints. For the first pair in the constraints $$$(1, 3)$$$ the only path that meets this constraint is $$$1 \rightarrow 2 \rightarrow 3$$$. On the other hand, for the second pair in the constraints $$$(5, 4)$$$, there is no path that can start from $$$5$$$ and end at $$$4$$$. So we can say that $$$\textit{Abdullah}$$$ is a Liar because there is a contradiction, that's why we provide "NO".