#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 9;
const int mod = 1e9 + 7;
#define eps 1e-5
#define inf 2e18
int fa[N];
int find(int x) 
{
    return fa[x]=(fa[x]==x?x:find(fa[x]));
}
int n,m;
struct Edge
{
    int x,y,w;
    bool operator < (const Edge &m) const
    {
        if(w!=m.w) return w<m.w;
        if(x!=m.x) return x<m.x;
        return y<m.y; 
    }
};
vector<Edge> g;
int ind[N],rd[N];


void solve()
{
    cin>>n>>m;
    g.clear();
    for(int i=1;i<=n;++i) ind[i] = rd[i] = 0,fa[i] = i;
    for(int i=1;i<=m;++i)
    {
        int x,y;cin>>x>>y;
        if(x==y) continue;
        ind[y]++,ind[x]++;
        g.push_back({x,y,max(ind[y],ind[x])});
    }

    sort(g.begin(),g.end());
    
    vector<pair<int,int> > v;
     for(auto &[x,y,w] : g)
    {
        int fx = find(x),fy = find(y);
        if(fx==fy) continue;
        v.push_back({x,y});
        rd[y]++,rd[x]++;
        fa[fy]=fx;
    }
    
    bool ok=true;
    for(int i=1;i<=n;++i) if(rd[i] > n/2)
    {
        ok=false;
        break;
    }

    if(!ok)
    {
        cout<<"No"<<'\n';
        return ;
    }
    else 
    {
        cout<<"Yes"<<'\n';
        for(auto &[x,y]:v)
            cout<<x<<' '<<y<<'\n';
    }


}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;  cin>>_;
    while (_--) solve();
    return 0;
}