#include <bits/stdc++.h>
using namespace std;
int n, m, d;
vector<vector<int> > adj;
vector<int> edg, grp;
vector<bool> usd;
void f(int x, int g) {
  grp[x] = g;
  for (int v : adj[x]) {
    if (v == 1 || grp[v] != -1) continue;
    f(v, g);
  }
}
int main(void) {
  cin >> n >> m >> d;
  adj.assign(n + 1, vector<int>());
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  if (d > adj[1].size()) {
    puts("NO");
    return 0;
  }
  grp.assign(n + 1, -1);
  for (int i = 2; i <= n; i++) {
    if (grp[i] == -1) f(i, i);
  }
  int ngs = 0;
  vector<bool> ng(n + 1, false);
  for (int v : adj[1]) {
    if (!ng[grp[v]]) {
      ng[grp[v]] = true;
      ngs++;
    }
  }
  if (ngs > d) {
    puts("NO");
    return 0;
  }
  queue<int> q;
  usd.assign(n + 1, false);
  for (int v : adj[1]) {
    if (ng[grp[v]]) {
      ng[grp[v]] = false;
      edg.push_back(1);
      edg.push_back(v);
      usd[v] = true;
      q.push(v);
      d--;
    }
  }
  for (int v : adj[1]) {
    if (d == 0) break;
    if (!usd[v]) {
      edg.push_back(1);
      edg.push_back(v);
      usd[v] = true;
      q.push(v);
      d--;
    }
  }
  usd[1] = true;
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int y : adj[v]) {
      if (!usd[y]) {
        edg.push_back(v);
        edg.push_back(y);
        q.push(y);
        usd[y] = true;
      }
    }
  }
  puts("YES");
  for (int i = 0; i < n - 1; i++) {
    cout << edg[i * 2] << " " << edg[i * 2 + 1] << endl;
  }
}
