URI Online Judge | 1684

Candy Marathon

By Luís Dorelli, ICMC - USP BR Brazil

Timelimit: 3

It's time of the running marathons in the Land of Ooo again. Princess Bubblegum has got a map of the Candy Kingdom and now she's got to prepare the streets to hold the competitions.

Her task is the following: she needs to separate the streets of the kingdom in disjoint marathon circuits, i.e., serveral disjoint paths that begin and end in the same corner. Each street must be used in exactly one circuit, or else a great rage will fall upon the kingdom. She doesn't mind the number of circuits generated, as long as there is at least one, since the marathon can be adjusted to fit the resources available.

Bubblegum believes that if any task is possible, she can do it. The question therefore is: can the streets of the kingdom be divided into disjoint circuits?

Input

The first line will contain a number T (1 ≤ T ≤ 100), indicating how many test cases will follow.

Each test begins with a number, N (0 ≤ N ≤ 104), indicating the number of crossings in the kingdom and M (0 ≤ M ≤ 105), the number of streets.The next M lines contains two integers each, a and b (0 ≤ a,bN-1), indicating that there is a street between crossings a and b. There may be streets connecting a crossing to itself, and there might be more than one street connecting two crossings.

Output

Print Yes if the task is possible and No otherwise.

Sample Input Sample Output

4
2 1
1 0
5 6
0 4
3 0
4 3
2 3
1 3
1 2

7 8
0 1
0 2
2 3
1 3
3 4
4 5
5 6
6 3
7 9
0 1
0 2
2 3
1 3
3 4
4 5
5 6
6 3
2 1

No
Yes
Yes
No