Toy Alliances

You are going to play a mock war game with N animal toys. For convenience the toys are numbered 1 through N, and you want to divide them into two alliances. Some pairs of toys may dislike each other (for example a dog toy and a cat toy, or Batman and the Joker), and such a pair of toys cannot belong to the same alliance.

For example, suppose N = 3 and (1, 2), (2, 3), and (3, 1) cannot be allies. In this case, no matter how you divide the three toys into two alliances, one of the alliances has a pair of toys that cannot be allies, so the division is impossible. As another example, if N = 4 and the four pairs (1, 2), (2, 3), (3, 4), and (4, 1) are given, the toys can be divided into the two alliances {1, 3} and {2, 4}.

Given a total of M pairs of toys that cannot be allies for various reasons, you want to divide the N toys into two alliances so that every pair of toys that cannot be allies belongs to different alliances.

The first line gives the number of test cases T.

The first line of each test case gives N and M, separated by a space.

The following M lines each give one pair of toy numbers, separated by a space.

For each test case, print "YES" if the N toys can be divided into two alliances, and "NO" otherwise. (All uppercase, without quotation marks)

• 1 ≤ T ≤ 10
• The two toy numbers on a line are never equal in the input
• Within one test case, the same pair of toys is never given more than once in the input (for example, if x y is given once, neither x y nor y x appears again in the same test case)