#include <bits/stdc++.h>
using namespace std;
vector<long long> par(200005 + 1), w(200005 + 1, 0);
vector<long long> g[200005];
vector<bool> mark;
long long root(long long x) {
  while (x != par[x]) par[x] = par[par[x]], x = par[x];
  return x;
}
void union_node(long long x, long long y) {
  x = root(x);
  y = root(y);
  if (w[x] < w[y]) {
    w[y] += w[x];
    par[x] = y;
  } else {
    w[x] += w[y];
    par[y] = x;
  }
}
void init() {
  for (long long i = 0; i <= 200005; i++) par[i] = i;
}
int main(void) {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  srand(time(NULL));
  ;
  int t = 1;
  while (t--) {
    init();
    long long n, i, j, k, m, x, y, z, w, t1, t2, t3;
    cin >> n >> k >> m;
    vector<bool> v(n + 1, 0);
    mark.resize(n + 1, 0);
    for (i = 0; i < k; i++) {
      cin >> x >> y;
      g[x].push_back(y);
      g[y].push_back(x);
      if (x != 1 && y != 1) union_node(x, y);
    }
    y = 0;
    for (i = 1; i <= n; i++) {
      x = root(i);
      if (!mark[x]) mark[x] = 1, y++, v[x] = 1;
    }
    y--;
    if (m < y || m > (long long)g[1].size()) return cout << "NO", 0;
    cout << "YES\n";
    queue<long long> q;
    mark.clear();
    mark.resize(n + 1, 0);
    q.push(1);
    mark[1] = 1;
    for (i = 0; i < g[1].size(); i++) {
      x = root(g[1][i]);
      if (v[x] == 1)
        q.push(g[1][i]), v[x] = 0, mark[g[1][i]] = 1, m--,
                         cout << 1 << " " << g[1][i] << "\n";
    }
    while (!q.empty()) {
      x = q.front();
      if (x == 1)
        y = m;
      else
        y = g[x].size();
      for (i = 0; i < g[x].size() && y > 0; i++, j++) {
        if (!mark[g[x][i]])
          q.push(g[x][i]), mark[g[x][i]] = 1, y--,
                           cout << x << " " << g[x][i] << "\n";
      }
      q.pop();
    }
  }
  return 0;
}
