#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
struct star {
  int from, next, to, id;
};
int n, m, num[MAXN], fa[MAXN], d, head[MAXN], len;
star g[MAXN * 2];
bool choose[MAXN], vis[MAXN];
int getfather(int x) { return fa[x] == x ? x : fa[x] = getfather(fa[x]); }
void add(int x, int y) {
  x = getfather(x);
  y = getfather(y);
  fa[y] = x;
  return;
}
void init() {
  memset(head, -1, sizeof(head));
  len = 0;
  for (int i = 1; i <= n; ++i) {
    fa[i] = i;
  }
  memset(num, 0, sizeof(num));
  memset(choose, false, sizeof(choose));
  memset(vis, false, sizeof(vis));
}
void adde(int u, int v, int id) {
  g[++len].to = v;
  g[len].id = id;
  g[len].from = u;
  g[len].next = head[u];
  head[u] = len;
}
int main() {
  scanf("%d%d%d", &n, &m, &d);
  init();
  int need = n - 1 - d;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    ++num[u];
    ++num[v];
    adde(u, v, i);
    adde(v, u, i);
    if (u != 1 && v != 1) {
      add(u, v);
    }
  }
  int p = 0, p2 = 0;
  for (int i = 2; i <= n; ++i) {
    if (getfather(i) == i) {
      ++p;
    }
  }
  if (d < p || num[1] < p) {
    printf("NO\n");
    return 0;
  }
  for (int i = head[1]; i != -1; i = g[i].next) {
    if (getfather(1) != getfather(g[i].to)) {
      add(1, g[i].to);
      ++p2;
      --d;
      choose[g[i].id] = true;
    }
  }
  if (p != p2) {
    printf("NO\n");
    return 0;
  }
  for (int i = head[1]; i != -1 && d > 0; i = g[i].next) {
    if (!choose[g[i].id]) {
      choose[g[i].id] = true;
      --d;
    }
  }
  for (int i = 1; i <= n; ++i) {
    fa[i] = i;
  }
  for (int i = head[1]; i != -1; i = g[i].next) {
    if (choose[g[i].id]) {
      add(1, g[i].to);
    }
  }
  for (int i = 1; i <= len; i += 2) {
    if (g[i].from != 1 && g[i].to != 1 && !choose[g[i].id] &&
        getfather(g[i].from) != getfather(g[i].to)) {
      choose[g[i].id] = true;
      add(g[i].from, g[i].to);
      --need;
    }
  }
  if (need == 0) {
    printf("YES\n");
    for (int i = 1; i <= len; i += 2) {
      if (choose[g[i].id]) {
        printf("%d %d\n", g[i].from, g[i].to);
      }
    }
  } else {
    printf("NO\n");
  }
  return 0;
}
