#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

typedef long long LL;
//#define int LL
#define inl inline
const int N = 4e5 + 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;
    int id;
};
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)];
    }
};
int dep[N];
int d[N];
DSU dsu;
vector<Node>vec[N];
void dfs(int u,int fat,int t) {
    dsu.fa[u]=t;
    dep[u]=dep[fat]+1;
    for(auto [u,v,id]:vec[u]) {
        if(v==fat)continue;
        dfs(v,u,t);
    }
}

void solve() {
    cin>>n>>m;
    dsu.init(n+1);
    for(int i=0;i<=n;i++) {
        d[i]=0;
        vec[i].clear();
    }

    vector<int>vis(m+1,0);
    vector<int>to(m+1);

    for(int i=1;i<=m;i++) {
        auto &[u,v,id]=edge[i];
        cin>>u>>v;
        id=i;
    }

    for(int i=1;i<=m;i++) {
        auto [u,v,id]=edge[i];
        if(!dsu.same(u,v)) {
            dsu.merge(u,v);
            d[u]++;
            d[v]++;
            vec[u].push_back({u,v,id});
            vec[v].push_back({v,u,id});
            vis[i]=true;
        }
    }
    int root=0;
    for(int i=1;i<=n;i++) {
        if(d[i]>n/2)root=i;
    }
    if(!root) {
        cout<<"Yes"<<"\n";
        for(int i=1;i<=m;i++) {
            if(vis[i]) {
                cout<<edge[i].u<<" "<<edge[i].v<<"\n";
            }
        }
        return;
    }

    dsu.fa[root]=root;
    dep[root]=0;
    for(auto [u,v,id]:vec[root]) {
        to[v]=id;
        dfs(v,root,v);
    }

    for(int i=1;i<=m;i++) {
        auto [u,v,id]=edge[i];
        if(u==root||v==root)continue;
        int fa_u=dsu.find(u),fa_v=dsu.find(v);
        if(fa_u==fa_v) continue;
        if(dep[u]<dep[v]) {
            swap(u,v);
            swap(fa_u,fa_v);
        }
        if(dep[v]==1&&d[u]>d[v]) {
            swap(u,v);
            swap(fa_u,fa_v);
        }
        ++d[u],++d[v];
        --d[root],--d[fa_v];
        vis[id]=1;
        vis[to[fa_v]]=0;
        dsu.fa[fa_v]=fa_u;
        if(d[root]<=n/2)break;
    }

    for(int i=1;i<=n;i++) {
        if(d[i]>n/2) {
            cout<<"No"<<"\n";
            return;
        }
    }

    cout<<"Yes"<<"\n";
    for(int i=1;i<=m;i++) {
        if(vis[i]) {
            cout<<edge[i].u<<" "<<edge[i].v<<"\n";
        }
    }
}

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;
}