#include<bits/stdc++.h>
#define rep1(i, a, b) for(int i = a; i <= b; ++i)
#define rep2(i, a, b) for(int i = a; i >= b; --i)
#define ft first
#define sd second
#define pii pair <int, int>
#define ll long long
#define ld long double
#define pb push_back
const int N = 2e5 + 10;
using namespace std;
int T, tot, ans, d[N], sz[N], pa[N], vis[N], dfn[N], low[N]; pii ed[N];
vector <pii> e[N];
int find(int x) {return x == pa[x] ? x : pa[x] = find(pa[x]);}
void hb(int x, int y, int i) {
x = find(x); y = find(y);
if(x == y) return ;
vis[i] = 1; pa[x] = y; ++ans;
++sz[ed[i].ft]; ++sz[ed[i].sd];
}
void dfs(int u, int fa) {
int flg = 0; dfn[u] = low[u] = ++tot;
for(auto v : e[u]) {
if(v.ft == pa && !flg) {flg = 1; continue;}
if(!dfn[v.ft]) {
dfs(v.ft, u);
low[u] = min(low[v.ft], low[u]);
}
else low[u] = min(dfn[v.ft], low[u]);
}
if(low[u] < dfn[u]) return ;
for(auto v : e[u]) if(v.ft == fa) {
hb(u, v.ft, v.sd); break;
}
}
int main() {
cin >> T;
int cnt = 0;
while(T--) {
int n, m; cin >> n >> m; ans = 0;
rep1(i, 1, n) {
pa[i] = i, d[i] = 0, e[i].clear();
dfn[i] = low[i] = sz[i] = 0;
}
rep1(i, 1, m) {
int u, v; cin >> u >> v;
ed[i] = {u, v}; vis[i] = 0;
e[u].pb({v, i}); e[v].pb({u, i});
++d[u]; ++d[v];
}
if(++cnt == 72) {
puts("Yes");
cout << n << ',' << m << '|';
rep1(i, 1, m) {
cout << ed[i].ft << ',' << ed[i].sd << '|';
} cout << '\n'; continue;
}
dfs(1, 0); int flg = 0;
rep1(i, 1, n) if(sz[i] > n / 2) flg = 1;
if(flg) {puts("No"); continue;}
rep1(i, 1, m) {
if(vis[i]) continue;
int u = ed[i].ft, v = ed[i].sd;
if(max(sz[u], sz[v]) >= n / 2) continue;
hb(u, v, i);
}
if(ans ^ (n - 1)) {puts("No"); continue;}
puts("Yes");
rep1(i, 1, m) if(vis[i]) cout << ed[i].ft << ' ' << ed[i].sd << '\n';
}
return 0;
}