SPOJ Problem Set (classical) 10568. Graph Cut Problem code: GRAPHCUT

Given a graph G, and a subset of its vertices X. The associated cut of X is the set of edges
associated to X is the subset of all edges in G such that exactly one of the two vertices it joins
belongs to X.
In thinks, you will be given a graph and a subset of its edges, and you will have to determine
whether there exists a subset of the vertices of the graph for which the given subset of the edges
is its associated cut.

Input

The first line contains an integer T, the number of test cases (1 ≤ T ≤ 40). Each test case, consists of
a line which contains three integers N (2 ≤ N ≤ 500),E (1 ≤ E ≤ 104),K (1 ≤ K ≤ E), the number of
vertices in the graph, and the number of edges in the subset for which we want to know whether
it is an associated cut or not. Then, E lines follow, each of them contains two integers u,v (1 ≤ u,v ≤
N) which are the vertices joined by the edge, the first K of these E lines represent the asked subset.

Output

Output T lines, one for each test case. If the asked subset is an associated cut, then print “YES”,
otherwise print “NO”.

Example

Input:
2

3 3 1
1 2
2 3
1 3

12 17 6
3 4
5 6
10 11
1 5
6 10
4 8
1 2
2 3
6 7
7 8
9 10
11 12
5 9
2 6
3 7
7 11
8 12

Output:
NO
YES 

---

Added by:	Paulo Costa
Date:	2012-02-07
Time limit:	1s
Source limit:	50000B
Languages:	All
Resource:	UNI