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