#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
//#define int LL
#define inl inline
const int N = 3e5 + 10;
const int M = N * 2;
//const int mod=998244353;
const int mod = 1000000007;
const double eps = 1e-8;
//const int mod=1e9+7;
typedef pair<int, int> PII;
//const int INF=0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m;

void become_faster() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct Node {
    int u,v;
};
Node edge[N];

struct DSU {
    vector<int> fa, siz;

    DSU() {
    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        fa.resize(n);
        iota(fa.begin(), fa.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != fa[x]) {
            x = fa[x] = fa[fa[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        fa[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};
bool work() {
    DSU dsu(n+1);
    shuffle(edge+1,edge+1+m,std::mt19937{std::random_device{}()});
    vector<PII>res(n-1);
    vector<int>d(n+1,0);
    int idx=0;
    for(int i=1;i<=m;i++) {
        auto [u,v]=edge[i];
        if(!dsu.same(u,v)) {
            dsu.merge(u,v);
            res[idx++]={u,v};
            d[u]++;
            d[v]++;
            if(d[u]>n/2||d[v]>n/2)return false;
        }
    }
    cout<<"Yes"<<"\n";
    for(auto [t1,t2]:res)cout<<t1<<" "<<t2<<"\n";
    return true;
}
void solve() {
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        auto &[u,v]=edge[i];
        cin>>u>>v;
    }
    for(int i=1;i<=450;i++) {
        if(work()) {
            return;
        }
    }
    cout<<"No"<<endl;
}

signed main() {
    become_faster();
    int T = 1;
    //T=read();
    cin>>T;
    //for(int i=1;i<=100;i++)solve(i);
    while (T--) solve();
    return 0;
}