#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <random>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
const ll maxn = 2e3 + 1, maxm = 1e3 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31;
const ld eps = 1e-9;
int t, timer;
int n, m;
int dp[maxn], tin[maxn], used[maxn], color[maxn], colc[maxn], par[maxn];
vector<int> g[maxn], g2[maxn];
int foo[maxn], bar[maxn];
map<pair<int, int>, int> reb;
map<int, int> fix;
vector<int> ans;
void dfs(int v, int p){
used[v] = 1;
tin[v] = ++timer;
dp[v] = tin[v];
for (auto to : g[v]){
if (to != p){
if (used[to]){
dp[v] = min(dp[v], tin[to]);
}
else{
dfs(to, v);
dp[v] = min(dp[v], dp[to]);
if (dp[to] > tin[v]){
reb[mp(v, to)] = 1;
reb[mp(to, v)] = 1;
}
}
}
}
}
void dfs2(int v, int c){
used[v] = 1;
color[v] = c;
colc[c] += 1;
for (auto to : g2[v]){
if (used[to] == 0){
dfs2(to, c);
}
}
}
void dfs3(int v, int p, int root){
if ((int)ans.size() > 0){
return;
}
used[v] = 1;
for (auto to : g[v]){
if ((int)ans.size() > 0){
return;
}
if (color[to] != color[root] || fix[to] || to == p){
continue;
}
if (used[to] == 0){
par[to] = v;
dfs3(to, v, root);
}
else{
if (to == root){
while (v != to){
ans.pb(v);
v = par[v];
}
ans.pb(v);
return;
}
}
}
}
int main(){
cin >> t;
// cout << t << '\n';
while (t--){
cin >> n >> m;
for (int i = 1; i <= m; ++i){
cin >> foo[i] >> bar[i];
int u = foo[i], v = bar[i];
g[u].pb(v);
g[v].pb(u);
}
timer = 0;
for (int i = 1; i <= n; ++i){
g2[i].clear();
colc[i] = 0;
color[i] = 0;
used[i] = 0;
dp[i] = 0;
tin[i] = 0;
}
fix.clear();
ans.clear();
reb.clear();
//5 7
//3 5
//5 2
//2 4
//2 1
//4 3
//2 3
//1 4
for (int i = 1; i <= n; ++i){
if (used[i] == 0){
dfs(i, 0);
}
}
for (int i = 1; i <= m; ++i){
int u = foo[i], v = bar[i];
if (reb[mp(u, v)] == 0){
g2[u].pb(v);
g2[v].pb(u);
}
}
for (int i = 1; i <= n; ++i){
used[i] = 0;
}
int col = 0;
for (int i = 1; i <= n; ++i){
if (used[i] == 0){
dfs2(i, ++col);
}
}
for (int i = 1; i <= n; ++i){
used[i] = 0;
}
vector<pair<int, int>> answ;
for (int i = 1; i <= n; ++i){
if (colc[color[i]] > 1 && (int)g[i].size() >= 4){
for (int j = 0; j < 4 && (int)answ.size() == 0; ++j){
for (int k = j + 1; k < 4 && (int)answ.size() == 0; ++k){
for (int is = 1; is <= n; ++is){
used[is] = 0;
}
int u = g[i][j];
int v = g[i][k];
fix[u] = 1;
fix[v] = 1;
dfs3(i, -1, i);
if ((int)ans.size() > 0){
int nn = (int)ans.size();
for (int is = 0; is < nn; ++is){
answ.pb(mp(ans[is], ans[(is + 1) % nn]));
}
answ.pb(mp(i, u));
answ.pb(mp(i, v));
}
fix[u] = 0;
fix[v] = 0;
}
}
}
}
if ((int)answ.size() > 0){
cout << "YES\n";
cout << (int)answ.size() << '\n';
for (auto it : answ){
cout << it.f << " " << it.s << '\n';
}
}
else{
cout << "NO\n";
}
timer = 0;
for (int i = 1; i <= n; ++i){
g[i].clear();
g2[i].clear();
colc[i] = 0;
color[i] = 0;
used[i] = 0;
}
fix.clear();
ans.clear();
reb.clear();
}
}
/*
*/
1062B - Math | 1294C - Product of Three Numbers |
749A - Bachgold Problem | 1486B - Eastern Exhibition |
1363A - Odd Selection | 131B - Opposites Attract |
490C - Hacking Cypher | 158B - Taxi |
41C - Email address | 1373D - Maximum Sum on Even Positions |
1574C - Slay the Dragon | 621A - Wet Shark and Odd and Even |
1395A - Boboniu Likes to Color Balls | 1637C - Andrew and Stones |
1334B - Middle Class | 260C - Balls and Boxes |
1554A - Cherry | 11B - Jumping Jack |
716A - Crazy Computer | 644A - Parliament of Berland |
1657C - Bracket Sequence Deletion | 1657B - XY Sequence |
1009A - Game Shopping | 1657A - Integer Moves |
230B - T-primes | 630A - Again Twenty Five |
1234D - Distinct Characters Queries | 1183A - Nearest Interesting Number |
1009E - Intercity Travelling | 1637B - MEX and Array |