MINTRIAN - Minimal Triangulations of Graphs

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

Added by:Tomasz Goluch
Date:2008-02-05
Time limit:6.919s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET

hide comments
2022-12-20 22:01:29 Ishan
What are the constraints for n and m ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.