Background

Fanfan loves Arknights, and loves Mizuki and the Deepblue Tree even more. In the Year of the Dragon, he wants to build a Deepblue Tree that belongs only to him.

Problem Description

In a dream, in the hazy water shadows, Fanfan saw this Deepblue Tree that belongs only to him.

When the dream fell silent, he forgot everything, and only remembered that the tree has $n$ nodes.

Really? It seems not. There are $m$ things he still remembers clearly. The $i$-th thing is: the unique simple path (not repeating any node) between nodes $u_i$ and $v_i$ on this Deepblue Tree has exactly two edges.

Can you help Fanfan recall what this Deepblue Tree looks like? If there are multiple possibilities, you only need to output any one of them.

Of course, Fanfan can also wear out. Therefore, if you find that no matter what you do you cannot find a Deepblue Tree satisfying these $m$ things, you need to report that there is no solution.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case:

The first line contains two non-negative integers $n,m$, representing the number of nodes in the tree and the number of events in Fanfan's memory.

The next $m$ lines each contain two positive integers $u_i,v_i$, representing an event.

Output Format

For each test case:

• If there is no tree that satisfies the conditions, output No.
• Otherwise, output Yes on the first line, then output $n-1$ lines, each with a pair of positive integers $(u,v)$, representing the $n-1$ edges of the tree you give.

This problem uses a special judge, meaning that if there are multiple valid answers, you may output any one.

2
4 2
1 2
3 4
3 3
1 2
2 3
3 1

Yes
1 3
2 4
2 3
No

Hint

Sample $1$ Explanation

For the first test case, it is not hard to verify that the given tree satisfies the conditions.

For the second test case, it can be proved that no tree satisfies the conditions.

Constraints

For $100\%$ of the data, $1\le T\le 10^5$, $n\ge 2$, $m\ge 0$, $1\le \sum n\le 3\times 10^5$, $0\le \sum m\le 3\times 10^5$, $1\le u_i,v_i\le n$, $u_i\neq v_i$.

This problem uses bundled testdata.

Translated by ChatGPT 5