Jack's Socks

Jack is a scientist, which means he does not pay much attention to what he wears. He does not know the names of more than six colors and cannot tell subtly different shades apart. Today he is leaving for a conference, and he has just pulled a heap of unpaired socks out of the washing machine and must pair them up.

Jack can tell whether two socks look similar, and he is only willing to put two socks together as a pair if they seem similar to him. However, the similarity relation is not necessarily transitive: Jack may find sock A similar to B and B similar to C, yet be able to tell A and C apart and consider them not similar.

Jack wants to know whether there is exactly one way to pair up all of his socks so that every pair consists of two similar socks. Write a program that decides this and, when the pairing is unique, prints it.

The first line contains a positive integer $Z \le 50$, the number of test cases. Then $Z$ test cases follow.

The first line of each test case contains two integers $n$ and $m$, separated by a single space ($1 \le n \le 1000$, $0 \le m \le 10000$). $n$ is even and is the number of socks, which are numbered from $1$ to $n$. Each of the next $m$ lines contains two different integers $a_i$ and $b_i$ ($a_i \ne b_i$), separated by a single space, meaning that socks $a_i$ and $b_i$ are similar. Every similar pair is listed exactly once: if $(a_i, b_i)$ appears, then neither $(a_i, b_i)$ nor $(b_i, a_i)$ appears again.

For each test case, decide whether there is exactly one way to pair all of the socks so that each pair consists of two similar socks.

If there is no such pairing, or more than one, print a single line containing NO.

Otherwise print YES on the first line, followed by $n/2$ lines describing the unique pairing. Each line contains one pair $c\ d$ with $c < d$, and the pairs must be sorted in increasing order of their first element: for any two consecutive pairs $(c, d)$ and $(e, f)$, $c < e$.