#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, d, c[N], deg;
vector<int> g[N];
bool vis[N], visc[N];
void dfs(int x, int comp) {
  if (vis[x]) return;
  vis[x] = true;
  c[x] = comp;
  for (auto& y : g[x]) {
    dfs(y, comp);
  }
}
void bfs(int x) {
  queue<int> q;
  q.push(x);
  vis[x] = true;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    vis[i] = false;
  }
  while (!q.empty()) {
    int to = q.front();
    q.pop();
    if (to == 1) {
      for (auto& y : g[1]) {
        if (!visc[c[y]]) {
          visc[c[y]] = true;
          cnt++;
          vis[y] = true;
          printf("1 %d\n", y);
          q.push(y);
        }
      }
      for (auto& y : g[1]) {
        if (cnt < d && !vis[y]) {
          cnt++;
          vis[y] = true;
          printf("1 %d\n", y);
          q.push(y);
        }
      }
    } else {
      for (auto& y : g[to]) {
        if (!vis[y]) {
          vis[y] = true;
          printf("%d %d\n", to, y);
          q.push(y);
        }
      }
    }
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &d);
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (x > y) swap(x, y);
    if (x == 1) {
      g[x].push_back(y);
      deg++;
      continue;
    }
    g[x].push_back(y);
    g[y].push_back(x);
  }
  if (d > deg) {
    printf("NO\n");
    return 0;
  }
  int comp = 0;
  for (int i = 2; i <= n; i++) {
    if (!vis[i]) {
      dfs(i, ++comp);
    }
  }
  if (comp > d) {
    printf("NO\n");
    return 0;
  } else {
    printf("YES\n");
    bfs(1);
  }
  return 0;
}
