Q21: Warcraft Tournament

RESUBMIT YOUR Q21 as Q24 please!!!

There is a WarCraft tournament in Sesame Street that consist of numerous matches. Each game is played between two players, and there is always a winner (i.e. no ties). At the end of the tournament, the player who wins the largest number of games wins the tournament. (we may have people tie for champion). Due to time constraints, not everyone gets to play everyone else in the tournament. There are at most 50 players, and 100 games in total.

The matches are announced up front, and Ernie would like to know if he still has a chance of winning halfway through the tournament. Ernie knows the results of all the games that have been played. He also knows about who is playing who in the upcoming matches. Give an algorithm to determine if Ernie can still somehow win. Note: There may be more than one match between two contestants, e.g. Big Bird may get to play everyone twice!

For example, if Bert has beaten Elmo and Oscar before, and only two games are left: Bert vs. Ernie, Elmo vs. Oscar. Then, Ernie cannot hope to win, even if he beats Bert in the next match.

Submit this problem in the judge as "Q21"

INPUT

There will be multiple test cases. The first line will contain an integer numCase equal to the number of test cases.
For each test case, the first line will contain three integers n a b. n is the number of players in the tournament, numbered from 0 to n - 1. Ernie is player 0. a is the number of matches that have been played, and b is the number of upcoming matches. The following a lines describes the previous matches with two integers u, v, which means player u beats player v in that match. After that, b more lines decribes the upcoming matches with two integers u, v, which means player u plays against player v in that match.

OUTPUT

For each test case, output "YES" if Ernie (player 0) can still hope to win the tournament. Otherwise, output "NO".

Sample Input

3
7 6 2
1 2
2 3
3 1
4 5
5 6
6 4
0 1
1 4
8 4 4
0 1
2 3
5 6
5 7
0 2
0 5
2 4
2 5
3 1 1
1 0
1 2

Sample Output

NO
YES
NO