#include <bits/stdc++.h>

using i64 = long long;

struct DSU {
    std::vector<int> fa, sz;
    DSU(int n = 0) {
        init(n);
    }
    void init(int n) {
        fa.resize(n);
        std::iota(fa.begin(), fa.end(), 0);
        sz.assign(n, 1);
    }
    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[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;
        }
        fa[y] = x;
        sz[x] += sz[y];
        return true;
    }
    int size(int x) {
        return sz[find(x)];
    }
};

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

    std::vector<std::pair<int, int>> edges;
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;
        edges.emplace_back(u, v);
    }

    DSU dsu(n);
    std::vector<int> deg(n);
    std::vector<std::vector<int>> adj(n);
    for (auto [u, v] : edges) {
        if (dsu.merge(u, v)) {
            deg[u] += 1;
            deg[v] += 1;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }

    int rt = std::max_element(deg.begin(), deg.end()) - deg.begin();
    std::vector<int> fa(n, -1);
    auto dfs = [&](auto self, int u) -> void {
        for (auto v : adj[u]) {
            if (v == fa[u]) {
                continue;
            }
            fa[v] = u;
            self(self, v);
        }
    };
    dfs(dfs, rt);

    std::vector<bool> del(n);
    std::vector<std::pair<int, int>> ans;
    del[rt] = true;
    if (deg[rt] > n / 2) {
        dsu.init(n);
        for (int u = 0; u < n; ++u) {
            if (u != rt && fa[u] != rt) {
                dsu.merge(fa[u], u);
            }
        }
        for (auto [u, v] : edges) {
            if (u != rt && v != rt && dsu.find(u) != dsu.find(v)) {
                int x = dsu.find(u);
                int y = dsu.find(v);
                if (deg[x] > deg[y]) {
                    std::swap(x, y);
                    std::swap(u, v);
                }
                dsu.merge(x, y);
                del[y] = true;
                ans.emplace_back(u, v);
                deg[rt] -= 1;
                deg[y] -= 1;
                deg[u] += 1;
                deg[v] += 1;
                if (deg[rt] <= n / 2) {
                    break;
                }
            }
        }
        if (*std::max_element(deg.begin(), deg.end()) > n / 2) {
            std::cout << "No\n";
            return;
        }
    }

    std::cout << "Yes\n";
    for (int u = 0; u < n; ++u) {
        if (!del[u]) {
            std::cout << fa[u] + 1 << " " << u + 1 << "\n";
        }
    }
    for (auto [u, v] : ans) {
        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;
}