#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popc(x) (__builtin_popcountll((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
const int N = 2e5+25;
int n,m;
int deg[N];
pair<int,int> G[N];
int p[N];
int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); }
void Union(int x,int y) { if((x=Find(x))!=(y!=Find(y))) p[y]=x; }
signed main() {
#ifndef ONLINE_JUDGE
#endif
   cin.tie(nullptr)->sync_with_stdio(false);
   int T; cin>>T; while(T--)
   Solve();
}
void Solve() {
   cin>>n>>m;
   iota(p+1,p+n+1,1),fill(deg+1,deg+n+1,0);
   vector<pair<int,int>> ans;
   for(int i=1;i<=m;i++) {
      int u,v; cin>>u>>v;
      if(u==v) { --i,--m; continue; }
      G[i]={u,v};
      if(Find(u)!=Find(v)) {
         ++deg[u],++deg[v];
         Union(u,v);
         ans.emplace_back(u,v);
      }
   }
   int rt=-1;
   for(int i=1;i<=n;i++) if(deg[i]>n/2) rt=i;
   if(!~rt) {
      puts("Yes");
      for(auto E:ans) printf("%d %d\n",E.first,E.second);
      return ;
   }
   iota(p+1,p+n+1,1);
   vector<int> son;
   vector<pair<int,int>> tans; tans.swap(ans);
   for(auto E:tans) {
      int u,v; tie(u,v)=E;
      if(u==rt||v==rt) {
         son.emplace_back(u==rt?v:u);
         continue;
      }
      if(Find(u)!=Find(v)) {
         Union(u,v);
         ans.emplace_back(u,v);
      }
   }
   for(int i=1;i<=m;i++) {
      int u,v; tie(u,v)=G[i];
      if(u==rt||v==rt||Find(u)==Find(v)) continue;
      Union(u,v);
      ++deg[u],++deg[v];
      ans.emplace_back(u,v);
      if(--deg[rt]<=n/2) break;
   }
   for(auto x:son) if(Find(x)!=Find(rt)&&deg[x]<=n/2)
      Union(x,rt),ans.emplace_back(x,rt);
   assert(ans.size()>n-1);
   if(ans.size()!=n-1) return void(puts("No"));
   puts("Yes");
   for(auto E:ans) printf("%d %d\n",E.first,E.second);
}