Sheila is participating in a crafts competition. She is given beads of two colors- blue and green. Beads are numbered from 1,2,…n. Her task is to connect beads and make a pattern. She is given a list of pairs of beads that should be connected. However, Sheila does not like the pattern if two beads of the same color need to be connected. Given a list of beads that should be connected, your task is to print “Yes” if it is possible to make a pattern that Sheila likes and “No” if it is not possible.
Input:
The first line contains T ,the number of test cases. The first line of each test case consists of 2 integers: n, the number of beads Sheila has and m, the number of connections she has to make. It is followed by m lines, each consisting of two integers i and j, indicating that beads numbered i and j should be connected.
Output:
Print a single line of output, “Yes” if Sheila can make a pattern that she likes and “No” otherwise.
Constraints:
For test case 1, there are 3 beads and 3 connections. For Sheila to like it, 1 and 2 should be of different color and 2 and 3 to be of different color. Since Sheila uses has only two colors and beads 1 and 3 should be connected, they will be of same color (see Fig.1). So Sheila cannot make a pattern that she likes.For test case 2, it is possible to make such a pattern(see Fig. 2).
