1386 - Jack

Time Limit : 2 Second

Memory Limit : 128 MB

Submission: 46

Solved: 12

Description


Jack is a scientist. As you probably realize, this means he does not pay much attention to what he wears daily. He is also a man, which means that he knows the names of no more than six colors, cannot

tell the difference between ecru and white and associates plum only with fruits. But today he is leaving for a conference. He has just pulled a set of single socks out of washing machine and must pair them.

He can say which sock is similar to which one, and he may pair only these socks which seem similar. However, many socks are similar to many others. Worse than that, similarity relation is not necessarily

transitive. For example, for Jack blue feels similar to seagreen and seagreen to green, but Jack can distinguish between blue and green and say that they are not similar.



Jack wonders if there is exactly one way to pair all his socks. Help him by writing an appropriate program. Do not worry: he might be a scientist, but he is not going to wear his socks with sandals.


Input


Multiple Test Cases

The input contains several test cases. The first line of the input contains a positive integer Z <=  50, denoting the number of test cases. Then Z test cases follow, each conforming to the format described in section Single Instance Input. For each test case, your program has to write an output conforming to the format described in section Single Instance Output.



Single Instance Input

The first line of input instance contains two integers n and m separated by a single space, where 1 <= n <= 1000 and 0 <= m <= 10000. Number n is even and denotes the number of socks; they are numbered from 1 to n. Each of the following m lines contains two numbers ai != bi separated by a single space, which means that socks ai and bi are similar. Each similarity pair is listed exactly once, i.e., if (ai, bi)

occurs, then neither (ai, bi) nor (bi, ai) appears later in this list. 


Output


Single Instance Output

For each input instance your program should check whether there exists exactly one way of pairing all these socks. If not, it should output a line containing NO. Otherwise, it should output YES in the first

line, followed by n/2 lines, each containing a sock pair from this pairing separated by a single space. Pairs should be output in sorted order, i.e., for each pair (c, d), it should hold that c < d and for any two consecutive pairs (c, d) and (e, f), c < e.


sample input
2
4 4
1 2
2 3
3 4
4 1
4 3
1 2
2 3
3 4
sample output
NO
YES
1 2
3 4
hint
source
Central European Programming Contest 2009
© 2015 HUST ACMICPC TEAM. All Right Reserved.