#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
const int maxm = 2e5 + 10;
int n, m, d, deg[maxn], p[maxn];
int find(int first) {
  return p[first] == first ? p[first] : p[first] = find(p[first]);
}
struct I {
  int u, v, w;
} e[maxn];
int main() {
  cin >> n >> m >> d;
  for (int i = 1, a, b; i <= m; ++i) {
    cin >> e[i].u >> e[i].v;
    if (e[i].u == 1 || e[i].v == 1) e[i].w = INF;
    ++deg[e[i].u];
    ++deg[e[i].v];
  }
  sort(e + 1, e + m + 1, [](I a, I b) { return a.w < b.w; });
  for (int i = 1; i <= n; ++i) p[i] = i;
  int cnt = 0;
  for (int i = 1; i <= m; ++i) {
    int fa = find(e[i].u);
    int fb = find(e[i].v);
    if (fa != fb) {
      p[fa] = fb;
      if (e[i].w == INF) {
        e[i].w = -1;
        ++cnt;
      }
    }
  }
  if (cnt > d || deg[1] < d) {
    cout << "NO" << '\n';
    return 0;
  }
  for (int i = 1; i <= m; ++i) {
    if (e[i].w == INF)
      e[i].w = 0;
    else if (!e[i].w)
      e[i].w = 1;
  }
  sort(e + 1, e + m + 1, [](I a, I b) { return a.w < b.w; });
  for (int i = 1; i <= n; ++i) p[i] = i;
  vector<pair<int, int> > ans;
  for (int i = 1; i <= m; ++i) {
    int fa = find(e[i].u);
    int fb = find(e[i].v);
    if (fa != fb && ((e[i].w <= 0 && d) || e[i].w)) {
      p[fa] = fb;
      if (e[i].w <= 0) --d;
      ans.push_back({e[i].u, e[i].v});
    }
  }
  if (d != 0) {
    cout << "NO" << '\n';
    return 0;
  }
  cout << "YES" << '\n';
  for (auto v : ans) printf("%d %d\n", v.first, v.second);
  return 0;
}
