#include <bits/stdc++.h>
using namespace std;
int n, m, d;
const int maxn = 200001;
vector<int> lab;
vector<pair<int, int> > e1, e;
void enter() {
  cin >> n >> m >> d;
  for (int i = 0, u, v; i < m; i++) {
    cin >> u >> v;
    if (u > v) swap(u, v);
    if (u == 1) {
      e1.push_back({u, v});
    } else {
      e.push_back({u, v});
    }
  }
}
vector<bool> need;
int root(int u) {
  if (lab[u] < 0) return u;
  return lab[u] = root(lab[u]);
}
void mtree(int ru, int rv) {
  if (lab[ru] > lab[rv]) swap(ru, rv);
  lab[ru] += lab[rv];
  lab[rv] = ru;
}
void init() { lab.assign(n + 1, -1); }
int main() {
  enter();
  need.assign(e1.size(), false);
  if (d > e1.size()) {
    cout << "NO";
    return 0;
  }
  init();
  int cc = n - 1;
  for (int i = 0; i < e.size(); i++) {
    int u = e[i].first, v = e[i].second;
    int ru = root(u), rv = root(v);
    if (ru != rv) {
      mtree(ru, rv);
      cc--;
    }
  }
  if (d < cc) {
    cout << "NO";
    return 0;
  }
  cout << "YES\n";
  int used = 0;
  for (int i = 0; i < e1.size(); i++) {
    int u = e1[i].first, v = e1[i].second;
    int ru = root(u), rv = root(v);
    if (ru != rv) {
      mtree(ru, rv);
      need[i] = true;
      used++;
    }
  }
  init();
  for (int i = 0; i < e1.size(); i++) {
    if (need[i]) {
      cout << e1[i].first << " " << e1[i].second << endl;
      int ru = root(1), rv = root(e1[i].second);
      mtree(ru, rv);
    } else {
      if (used < d) {
        used++;
        int ru = root(1), rv = root(e1[i].second);
        cout << e1[i].first << " " << e1[i].second << endl;
        mtree(ru, rv);
      }
    }
  }
  for (int i = 0; i < e.size(); i++) {
    int u = e[i].first, v = e[i].second;
    int ru = root(u), rv = root(v);
    if (ru != rv) {
      mtree(ru, rv);
      cout << e[i].first << " " << e[i].second << endl;
    }
  }
  return 0;
}
