#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int head[maxn], father[maxn], n, cnt, belong[maxn], tot, deg[maxn], perm[maxn],
    rankk[maxn];
bool vis[maxn];
vector<int> conn[maxn];
bool cmp(int a, int b) { return deg[a] < deg[b]; }
struct edge {
  int u, v, nxt;
} Edge[2 * maxn];
void init() {
  memset(head, -1, sizeof(head));
  memset(belong, 0, sizeof(belong));
  for (int i = 0; i <= n; i++) father[i] = i;
  cnt = 0, tot = 0;
}
int query(int id) { return father[id] == id ? id : query(father[id]); }
void merge(int x, int y) {
  x = query(x);
  y = query(y);
  if (x != y) {
    if (rankk[x] > rankk[y])
      father[y] = x;
    else {
      father[x] = y;
      if (rankk[x] == rankk[y]) rankk[y]++;
    }
  }
}
void addedge(int u, int v) {
  Edge[cnt].u = u;
  Edge[cnt].v = v;
  Edge[cnt].nxt = head[u];
  head[u] = cnt++;
}
void dfs(int id) {
  if (vis[id]) return;
  vis[id] = true;
  belong[id] = tot;
  for (int i = head[id]; i != -1; i = Edge[i].nxt) {
    int v = Edge[i].v;
    if (v == 1) {
      deg[tot]++;
      conn[tot].push_back(id);
      continue;
    }
    dfs(v);
  }
}
int main() {
  int m, u, v, d;
  scanf("%d%d%d", &n, &m, &d);
  init();
  int degone = 0;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &u, &v);
    addedge(u, v);
    addedge(v, u);
    degone += (u == 1 || v == 1);
  }
  for (int i = 2; i <= n; i++) {
    if (!vis[i]) {
      tot++;
      dfs(i);
    }
  }
  if (tot > d || degone < d) {
    printf("NO\n");
    return 0;
  }
  for (int i = 1; i <= tot; i++) perm[i] = i;
  int num = 0;
  printf("YES\n");
  for (int i = 1; i <= tot; i++) {
    int id = perm[i];
    num++;
    printf("%d %d\n", 1, conn[id][0]);
    merge(1, conn[id][0]);
    if (num == d) break;
  }
  for (int i = 1; i <= tot; i++) {
    int id = perm[i];
    for (int j = 1; j < conn[id].size(); j++) {
      if (num >= d) break;
      num++;
      printf("%d %d\n", 1, conn[id][j]);
      merge(1, conn[id][j]);
    }
    if (num >= d) break;
  }
  for (int i = 1; i <= cnt; i++) {
    u = Edge[i].u;
    v = Edge[i].v;
    if (u == 1 || v == 1) continue;
    if (query(u) != query(v)) {
      printf("%d %d\n", u, v);
      merge(u, v);
    }
  }
  return 0;
}
