#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    std::vector<int> fa(n, -1), dep(n), deg(n), mn(n, -1);
    std::vector<std::vector<int>> e(n);
    auto cmp = [&](int x, int y) {
        if (x == -1 || y == -1) {
            return x > y;
        }
        return dep[x] < dep[y];
    };
    auto dfs = [&](auto self, int u) -> void {
        for (auto v : adj[u]) {
            if (deg[v] == 0) {
                fa[v] = u;
                dep[v] = dep[u] + 1;
                deg[u] += 1;
                deg[v] += 1;
                e[u].push_back(v);
                self(self, v);
            } else if (dep[v] < dep[u]) {
                mn[u] = std::min(mn[u], v, cmp);
            }
        }
    };
    dfs(dfs, 0);

    std::vector<bool> del(n);
    std::vector<std::pair<int, int>> edges;
    int x = std::max_element(deg.begin(), deg.end()) - deg.begin();
    if (deg[x] > n / 2) {
        std::vector<std::array<int, 2>> f(n, {-1, -1});
        auto dfs2 = [&](auto self, int u) -> void {
            if (cmp(mn[u], x)) {
                if (deg[u] + (fa[u] != x) <= n / 2) {
                    f[u][0] = u;
                }
                if (deg[u] + 1 <= n / 2) {
                    f[u][1] = u;
                }
            }
            for (auto v : e[u]) {
                self(self, v);
                for (auto x : {0, 1}) {
                    if (f[v][x] != -1 && (f[u][x] == -1 || cmp(mn[f[v][x]], mn[f[u][x]]))) {
                        f[u][x] = f[v][x];
                    }
                }
            }
        };

        std::pair<int, int> mx{0, -1};
        for (auto u : e[x]) {
            dfs2(dfs2, u);
            if (f[u][0] == -1) {
                continue;
            }
            deg[x] -= 1;
            if (mn[f[u][0]] == fa[x]) {
                deg[fa[x]] += 1;
            }
            if (f[u][1] != -1) {
                mx = std::max(
                    mx, std::make_pair((mn[f[u][0]] == fa[x]) + (mn[f[u][1]] != fa[x]), u));
            }
        }
        if (fa[x] != -1) {
            deg[fa[x]] -= mx.first;
        }
        if (*std::max_element(deg.begin(), deg.end()) > n / 2) {
            std::cout << "No\n";
            return;
        }
        for (auto u : e[x]) {
            if (f[u][0] == -1) {
                continue;
            }
            if (u == mx.second) {
                del[u] = true;
                edges.emplace_back(mn[f[u][0]], f[u][0]);
            } else {
                del[f[u][0]] = true;
                edges.emplace_back(mn[f[u][0]], f[u][0]);
            }
        }
    }

    std::cout << "Yes\n";
    for (int u = 1; u < n; ++u) {
        std::cout << (del[u] ? mn[u] : fa[u]) + 1 << " " << u + 1 << "\n";
    }
    for (auto [u, v] : edges) {
        std::cout << u + 1 << " " << v + 1 << "\n";
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}