#include <bits/stdc++.h>
#pragma GCC optimize(2)
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)];
    }
};

int getRand(int min, int max) {
    return (rand() % (max - min + 1)) + min;
}

void solve() {
    cin >> n >> m;
    vector<vector<int> > g(n + 1);
    for (int i = 1; i <= m; i++) {
        auto &[u,v] = edge[i];
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> d(n + 1, 0);
    DSU dsu(n+1);
    vector<PII>res;
    int sign=1;
    auto dfs = [&](auto &self, int u, int fa)-> void {
        if(!sign)return;
        if (fa) {
            res.push_back({u,fa});
            d[u]++;
            d[fa]++;
            if(d[u]>n/2||d[fa]>n/2)sign=0;
        }
        for(auto v:g[u]) {
            if(v==fa)continue;
            if(dsu.same(u,v))continue;
            dsu.merge(u,v);
            self(self,v,u);
        }
    };

    auto work = [&]() {
        for (int i = 1; i <= n; i++)shuffle(g[i].begin(), g[i].end(), std::mt19937{std::random_device{}()});
        srand(time(0));
        int root = getRand(1, n);
        d.assign(n+1,0);
        dsu.init(n+1);
        res.clear();
        sign=1;
        dfs(dfs,root,0);
        return sign==1;
    };
    for (int i = 1; i <= 200; i++) {
        if (work()) {
            cout<<"Yes"<<"\n";
            for(auto [t1,t2]:res) {
                cout<<t1<<" "<<t2<<"\n";
            }
            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;
}