Description

A simple cycle is a closed simple path, with no other repeated vertices or edges other than the starting and ending vertices. The length of a cycle is the number of vertices on it. Given an undirected graph G(V, E), you are to detect whether it contains a simple cycle of length K. To make the problem easier, we only consider cases with small K here.

Input

There are multiple test cases.
The first line will contain a positive integer T (T ≤ 10) meaning the number of test cases.
For each test case, the first line contains three positive integers N, M and K ( N ≤ 50, M ≤ 500, 3 ≤ K ≤ 7). N is the number of vertices of the graph, M is the number of edges and K is the length of the cycle desired. Next follow M lines, each line contains two integers A and B, describing an undirected edge AB of the graph. Vertices are numbered from 0 to N-1.

Output

For each test case, you should output “YES” in one line if there is a cycle of length K in the given graph, otherwise output “NO”.

Sample Input

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

Sample Output

YES
NO

HINT

?

Source

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include