#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) {
    dfn[u] = low[u] = ++tot;
    for(auto v : e[u]) if(v.ft ^ fa) {
        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 == 143) {
            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;
}