#include <bits/stdc++.h>

using namespace std;

const int N = 310000;
int t, n, m, cnta, cntb, a[N], b[N], bel[N];
vector<int> edges[N];
bool vis[N];

inline void dfs(int p) {
    bel[p] = 3;
    a[++cnta] = p;
    for (auto y : edges[p]) if (!bel[y]) 
        dfs(y);
}

int main() {
    scanf("%d", &t);
    for (; t--; ) {
        cnta = cntb = 0;
        memset(bel, 0, sizeof(bel));
        memset(vis, false, sizeof(vis));
        scanf("%d%d", &n, &m);
        if (n == 1 && m == 0) {
            puts("Yes");
            continue;
        }
        for (int i = 1; i <= n; i++)
            edges[i].clear();
        for (; m--; ) {
            int u, v;
            scanf("%d%d", &u, &v);
            edges[u].push_back(v);
            edges[v].push_back(u);
            if (u == 1) {
                bel[u] = 1;
                a[++cnta] = v;
                bel[v] = 3;
            }
            else if (v == 1) {
                bel[v] = 1;
                a[++cnta] = u;
                bel[u] = 3;
            }
        }
        for (int i = 1; i <= n; i++) if (bel[i] == 3)
            dfs(i);
        for (int i = 1; i <= n; i++) if (!bel[i]) {
            b[++cntb] = i;
            bel[i] = 2;
        }
        if (!cntb && cnta)
            puts("No");
        else {
            bool f = true;
            for (int i = 1; i <= n && f; i++) for (auto y : edges[i]) {
                if (bel[i] == 1 && bel[y] == 2) 
                    f = false;
                else if (bel[i] == 2 && bel[y] == 1) 
                    f = false;
                else if (bel[i] == 2 && bel[y] == 3)
                    f = false;
                else if (bel[i] == 3 && bel[y] == 2) 
                    f = false;
            }
            if (!f) {
                puts("No");
                continue;
            }
            puts("Yes");
            for (int i = 1; i <= cntb; i++) if (!vis[b[i]]) {
                printf("1 %d\n", b[i]);
                vis[b[i]] = true;
            }
            memset(vis, false, sizeof(vis));
            for (int i = 1; i <= cnta; i++) if (!vis[a[i]]) {
                printf("%d %d\n", b[1], a[i]);
                vis[a[i]] = true;
            }
        }
    }
    return 0;
}