A wolf, a sheep and cabbage

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The following is an easy game that the setter of this problem played when he was 8:
A boatman, a wolf, a sheep, and a cabbage are on the bank of a river. They have a small boat that is capable of carrying the boatman and at most one other animal/item with him. However, if left alone by the boatman, the wolf can eat the sheep, and the sheep can eat the cabbage. How can all four be moved safely to the opposite bank of the river?
Here is a nice visualization of the whole process in the original game. Disclaimer: writers, testers and CodeChef are not related to this link.
This leads to a more general problem. If there are other groups of animals/items with the boatman, is it possible to move them all to the opposite bank of the river in such a way that nobody/nothing gets eaten?
We will give you the number of animals/items (not including the boatman). Moreover, we will give you all a list of pairs of the form "X Y" where the Xth animal/item will be eaten by the Yth one if they are both on the opposite bank to the boatman.
You are to determine whether it is possible to achieve the task or not.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test contains two space separated integers N and M  the number of animals/items not including the boatman, and the number of relations of the form "X will be eaten by Y", respectively.
The following M lines contain pairs of the form X Y with the meaning that the Xth animal/item will be eaten by the Yth one if they are both on the opposite bank to the boatman.
Output
For each test case, output a single line containing either "YES" or "NO"  the answer to the question "Is it possible to move them all to the opposite bank of the river in such a way that nobody/nothing gets eaten?".
Constraints
 1 ≤ T ≤ 100000
 Subtask 1: 1 ≤ N ≤ 5, 0 ≤ M ≤ 10  73 points.
 Subtask 2: 1 ≤ N ≤ 10, 0 ≤ M ≤ 20  27 points.
Example
Input: 2 3 2 1 2 2 3 3 3 1 2 2 3 1 3 Output: YES NO
Explanation
The first example is the original version of the problem.
The second example would have a solution if a boat could seat an additional animal/item.
Author:  xcwgf666 
Tester:  white_king 
Editorial  http://discuss.codechef.com/problems/WSC 
Tags  cakewalk, construction, language, ltime18, programming, xcwgf666 
Date Added:  10082014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 