#include <bits/stdc++.h>
using namespace std;
const int N = (int)2e5 + 8;
int n, m, d, d1, u[N], v[N];
struct dsu {
  int par[N], cntConnected;
  void init() {
    fill(par + 1, par + n + 1, -1);
    cntConnected = n;
  }
  int root(int u) { return (par[u] < 0 ? u : par[u] = root(par[u])); }
  bool Union(int u, int v) {
    if ((u = root(u)) == (v = root(v))) return false;
    if (par[u] > par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;
    --cntConnected;
    return true;
  }
} dsu1, dsu2;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cin >> n >> m >> d;
  for (int i = 0; i < m; ++i) {
    cin >> u[i] >> v[i];
    if (u[i] > v[i]) swap(u[i], v[i]);
    if (u[i] == 1) ++d1;
  }
  dsu1.init();
  for (int i = 0; i < m; ++i)
    if (u[i] != 1) dsu1.Union(u[i], v[i]);
  if (d1 < d || dsu1.cntConnected - 1 > d)
    cout << "NO";
  else {
    dsu2.init();
    cout << "YES\n";
    for (int i = 0; i < m && d; ++i)
      if (u[i] == 1 && dsu1.Union(u[i], v[i])) {
        cout << u[i] << ' ' << v[i] << '\n';
        ;
        dsu2.Union(u[i], v[i]);
        --d;
      }
    for (int i = 0; i < m && d; ++i)
      if (u[i] == 1 && dsu2.Union(u[i], v[i])) {
        cout << u[i] << ' ' << v[i] << '\n';
        ;
        --d;
      }
    for (int i = 0; i < m; ++i)
      if (u[i] != 1 && dsu2.Union(u[i], v[i]))
        cout << u[i] << ' ' << v[i] << '\n';
    ;
  }
}
