1209 - Playing games
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 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