#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second

using namespace std;

typedef pair<int,int> pii;
const int N = 2e5 + 10;
int n,m;
int f[N],deg[N];
bool vis[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline int find(int x){
    if (f[x] != x) return f[x] = find(f[x]);
    else return f[x];
}

inline void merge(int a,int b){
    int x = find(a),y = find(b);
    if (x == y) return;
    if (vis[x]) swap(x,y);
    f[x] = y;
}

inline void solve(){
    vector<pii> e1,e2;
    n = read(),m = read();
    // if ((++tot) == 120) cout << n << " " << m << " nm\n";
    fill(deg + 1,deg + n + 1,0);
    fill(vis + 1,vis + n + 1,false);
    for (re int i = 1;i <= n;i++) f[i] = i;
    for (re int i = 1,a,b;i <= m;i++){
        a = read(),b = read();
        // if (tot == 120) cout << a << " " << b << "\n";
        if (find(a) != find(b)){
            merge(a,b);
            // cerr << a << " " << b << " tree\n";
            deg[a]++; deg[b]++;
            e1.push_back({a,b});
        }
        else e2.push_back({a,b});
    }
    // if (tot > 2) return;
    int rt = 0;
    for (re int i = 1;i <= n;i++){
        if (deg[i] > n / 2) rt = i;
    }
    if (!rt){
        puts("Yes");
        for (pii p:e1) printf("%d %d\n",p.fst,p.snd);
        return;
    }
    for (re int i = 1;i <= n;i++) f[i] = i;
    for (pii p:e1){
        if (p.fst == rt) vis[p.snd] = true;
        else if (p.snd == rt) vis[p.fst] = true;
    }
    for (pii p:e1){
        if (p.fst != rt && p.snd != rt) merge(p.fst,p.snd);
    }
    for (pii p:e2){
        if (p.fst != rt && p.snd != rt && find(p.fst) != find(p.snd)){
            int x = find(p.fst),y = find(p.snd);
            if (deg[x] < deg[y]) swap(x,y);
            deg[x]--; deg[rt]--;
            deg[p.fst]++; deg[p.snd]++;
            if (deg[p.fst] > n / 2 || deg[p.snd] > n / 2){
                deg[x]++; deg[rt]++;
                deg[p.fst]--; deg[p.snd]--;
            }
            else{
                // cerr << p.fst << " " << p.snd << " ???\n";
                vis[x] = false; merge(x,y);
                e1.push_back(p);
            }
        }
    }
    if (deg[rt] > n / 2) puts("No");
    else{
        puts("Yes");
        for (pii p:e1){
            if (p.fst != rt && p.snd != rt) printf("%d %d\n",p.fst,p.snd);
        }
        for (re int i = 1;i <= n;i++){
            if (vis[i]) printf("%d %d\n",rt,i);
        }
    }
}

int main(){
    int T; T = read();
    while (T--) solve();
    return 0;
}