Check whether the given graph is chordal.

Input

The first line contains an integer 1<=t<=200 denoting the number of test cases. Then t graphs are given (not necessarily connected). Each graph is described by two lines. The first line contains a string of the form:

n=nodes,m=edges:

The second line gives the edges of the graph separated by commas. Each edge is given as a pair of vertices: {u,v}. Vertices of the graph are denoted with integers 0...,n-1.

Output

For each test case print YES if the graph is chordal, or NO if it isn't.

Example

Input:
2
n=6,m=4
{0,1} {2,3} {3,4} {3,5} 
n=6,m=7
{0,3} {1,2} {1,3} {2,4} {2,5} {3,4} {3,5} 

Output:
YES
NO