#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
#define debug puts("--------------------")
const int N = 2e5 + 10;
using namespace std;
int T, rt, d[N], pa[N], vis[N], id[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 u, int v, int i) {
    int x = find(u), y = find(v);
    if(x == y) return ;
//    cout << i << ' ' << u << ' ' << v << '\n';
//    ++d[u]; ++d[v];
    vis[i] = 1; pa[x] = y;
}
void dfs(int u, int fa) {
//	cout << u << ' ' << fa << '\n'; 
    for(auto v : e[u]) if(v.ft ^ fa && vis[v.sd]) {
        if(u ^ rt) hb(v.ft, u, v.sd);
        dfs(v.ft, u);
    }
}
int main() {
    cin >> T;
    int cnt = 0;
    while(T--) {
        int n, m; cin >> n >> m;
        rep1(i, 1, n) pa[i] = i, id[i] = d[i] = 0, e[i].clear();
        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});
            if(find(u) ^ find(v)) ++d[u], ++d[v];
			hb(u, v, i);
        }
//        if(++cnt == 120) {
//            puts("Yes");
//            cout << n << ',' << m << '|';
//            rep1(i, 1, m) {
//                cout << ed[i].ft << ',' << ed[i].sd << '|';
//            } cout << '\n'; continue;
//        }
        rt = 0;
//        debug;
        rep1(i, 1, n) {
            pa[i] = i;
            if(d[i] > d[rt]) rt = i;
        } dfs(rt, 0);
//        debug;
//        rep1(i, 1, n) cout << d[i] << " \n"[i == n];
        for(auto v : e[rt]) if(vis[v.sd]) id[v.ft] = v.sd;
        rep1(i, 1, m) {
            if(d[rt] <= n / 2) break;
            if(vis[i]) continue;
            int u = ed[i].ft, v = ed[i].sd;
//            if(max(d[u], d[v]) >= n / 2) continue;
            int x = find(u), y = find(v);
            if(x == y) continue;
            if(d[x] > d[y]) swap(x, y);
            vis[i] = 1; ++d[u]; ++d[v];
            vis[id[y]] = 0; --d[y]; --d[rt];
            pa[x] = y;
        }
        if(d[rt] > n / 2) {puts("No"); continue;}
        puts("Yes");
        rep1(i, 1, m) if(vis[i]) cout << ed[i].ft << ' ' << ed[i].sd << '\n';
    }
    return 0;
}
/*
1
9 19
3 8
3 7
3 4
9 8
6 4
3 4
1 3
2 6
4 8
3 9
3 6
3 9
3 2
3 6
5 3
6 3
1 3
3 4
7 9

1
5 9
5 2
4 3
3 2
4 5
3 4
1 2
1 3
4 2
2 5

2
6 9
1 2
1 3
1 4
2 3
2 4
3 4
4 5
4 6
4 6
3 4
1 3
2 3
3 3
1 2

1
5 12
2 5
2 4
4 1
2 2
4 2
1 4
2 3
2 2
2 5
2 3
4 2
5 4

*/