#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

vector<int> G[N], tG[N];
vector< pair<int, int> > T, E;
map< pair<int, int>, int> M;
mt19937 rnd;
int du[N];

void dfs(int x, int fa = -1)
{
    shuffle(G[x].begin(), G[x].end(), rnd);
    for (int i = 0; i < (int)G[x].size(); ++i) {
        int v = G[x][i];
        if (!du[v]) {
            T.push_back(make_pair(min(x, v), max(x, v)));
            tG[x].push_back(v);
            tG[v].push_back(x);
            ++du[x], ++du[v];
            dfs(v, x);
        } else if (v != fa) {
            if (!M.count(make_pair(min(x, v), max(x, v)))) {
                E.push_back(make_pair(min(x, v), max(x, v)));
                M[make_pair(min(x, v), max(x, v))] = 1;
            }
        }
    }
    return;
}

int col[N];

void color(int x, int c, int fa)
{
    col[x] = c;
    for (int i = 0; i < (int)tG[x].size(); ++i) {
        int v = tG[x][i];
        if (v != fa) {
            color(v, c, x);
        }
    }
    return;
}

int fa[N];

int find(int x)
{
    return (fa[x] == x ? x : fa[x] = find(fa[x]));
}

signed main()
{
    int TT;
    scanf("%d", &TT);
    while (TT--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            G[i].clear();
            tG[i].clear();
            du[i] = 0;
        }
        M.clear();
        while (m--) {
            int x, y;
            scanf("%d%d", &x, &y);
            if (x != y && !M.count(make_pair(min(x, y), max(x, y)))) {
                M[make_pair(min(x, y), max(x, y))] = 1;
                G[x].push_back(y);
                G[y].push_back(x);
            }
        }
        if (n == 2) {
            puts("Yes");
            puts("1 2");
            continue;
        }
        if (n == 3) {
            puts("No");
            continue;
        }
        M.clear();
        T.clear(), E.clear();
        dfs(1);
        int flag = 0;
        for (int i = 1; i <= n; ++i) {
            if (du[i] > n / 2) {
                flag = i;
                break;
            }
        }
        if (!flag) {
            puts("Yes");
            for (int i = 0; i < (int)T.size(); ++i) {
                printf("%d %d\n", T[i].first, T[i].second);
            }
            continue;
        }
        col[flag] = 0;
        for (int i = 0; i < (int)tG[flag].size(); ++i) {
            color(tG[flag][i], i + 1, flag);
            fa[i + 1] = i + 1;
        }
        set< pair<int, int> > res;
        for (int i = 0; i < (int)T.size(); ++i) {
            res.insert(T[i]);
        }
        for (int i = 0; i < (int)E.size() && du[flag] > n / 2; ++i) {
            int x = E[i].first, y = E[i].second;
            if (x == flag || y == flag || find(col[x]) == find(col[y])) {
                continue;
            }
            res.insert(E[i]);
            ++du[x], ++du[y];
            int c1 = tG[flag][find(col[x]) - 1], c2 = tG[flag][find(col[y]) - 1], wh = du[c1] > du[c2] ? c1 : c2;
            res.erase(make_pair(min(flag, wh), max(flag, wh)));
            --du[flag], --du[wh];
            if (1 || wh == c1) {
                fa[find(col[x])] = find(col[y]);
            } else {
                fa[find(col[y])] = find(col[x]);
            }
        }
        if (du[flag] <= n / 2) {
            puts("Yes");
            for (set< pair<int, int> >::iterator it = res.begin(); it != res.end(); ++it) {
                printf("%d %d\n", (*it).first, (*it).second);
            }
        } else {
            puts("No");
        }
    }
    return 0;
}