magical-graph-1

You are given a directed graph. However some edges have lost the direction in which they were facing. Now, you as a magician, want to direct each of the 
undirected edges in any of the two available directions.

For e.g., for an undirected edge (u,v) , you can convert it to directed edge u to v, or v to u.

But you hate cycles, so you want to make sure that there is no cycle in the graph after directing all the edges.
Is it possible to do that? If yes, print "Yes", else print "No".

Input Format:
First line contains T, number of Test Cases.
First line of each test contains N i.e. number of vertices,E1 i.e. number of directed edges, E2 i.e. number of undirected edges.
Next E1 lines contains two integers (u,v) denoting an directed edge from u to v.
Next E2 lines contains two integers (x,y) denoting an undirected edge between x and y.

Output Format:
Print "Yes" or "No" (without quotes) for each test case in a single line.

Constraints:
1 ≤ sum of N over all test cases ≤ 250000
1 ≤ sum of E1 over all test cases ≤ 250000
1 ≤ sum of E2 over all test cases ≤ 250000

Author: Sumeet Varma

SAMPLE INPUT
1
3 2 1
1 2
2 3
3 1

SAMPLE OUTPUT
Yes

Source: hackerearth | Difficulty: MEDIUM
Tags: Graph algorithms


Solutions: