1209 - Playing games

Time Limit: 1s Memory Limit: 128MB

Submissions: 133 Solved: 63
Description
In our childhood, we all like playing games with our friends. Now you are a teacher in a kindergarten and there are n children in your class. Before playing games, you must divide the children into some small groups and each group must contains more than one child, but a child only wants to stand besides his or her friends. k (k > 1) children can form a group only if there exists a circular permutation of k children in which each child only stand besides his or her friends. To make the problem simple, given you n children and the relationship between them, you must judge if every child can be divided into some group and no one will be left alone.
Input
In the first line of the input, there is an integer T (0 < T <= 20), which means T test cases. For each test case, the first line contains two integers n (0 < n <= 400) and m (0 < m < n*n/2), which are the number of the children and the number of the relationship. There are m lines followed, every line has two integers a and b (1 <= a, b <= n ), means child a and child b are friends..
Output
For each test case, if every child can be divided into some group and no child will be left alone, output "YES", or else output "NO".
Sample Input
2
4 2
1 2
3 4
3 2
1 2
1 3
Sample Output
YES
NO
Hint
Source