#include <bits/stdc++.h>
using namespace std;
const long long N = 200005;
long long root[N], qwertyui[N];
long long find(long long i) {
  if (i == root[i]) return i;
  return root[i] = find(root[i]);
}
long long join(long long u, long long v) {
  u = find(u);
  v = find(v);
  if (u == v) return false;
  if (qwertyui[u] > qwertyui[v]) swap(u, v);
  if (qwertyui[u] == qwertyui[v]) qwertyui[v]++;
  root[u] = v;
  return true;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, m, d;
  cin >> n >> m >> d;
  for (long long i = 1; i <= n; i++) {
    root[i] = i;
  }
  set<long long> s;
  vector<pair<long long, long long> > e;
  for (long long i = 1; i <= m; i++) {
    long long u, v;
    cin >> u >> v;
    if (u > v) swap(u, v);
    if (u == 1) {
      s.insert(v);
      qwertyui[v] = n;
    } else
      e.push_back(pair<long long, long long>(u, v));
  }
  if (s.size() < d) {
    cout << "NO" << '\n';
    return 0;
  }
  vector<pair<long long, long long> > r;
  for (auto i : e) {
    long long u = find(i.first), v = find(i.second);
    if (!(s.count(u) && s.count(v))) {
      if (join(u, v))
        r.push_back(pair<long long, long long>(i.first, i.second));
    }
  }
  long long t = s.size() - d;
  for (auto i : e) {
    if (t == 0) break;
    long long u = find(i.first), v = find(i.second);
    if (u != v) {
      join(u, v);
      r.push_back(pair<long long, long long>(i.first, i.second));
      t--;
    }
  }
  if (t) {
    cout << "NO" << '\n';
    return 0;
  }
  for (auto i : s) {
    if (join(1, i)) r.push_back(pair<long long, long long>(1, i));
  }
  cout << "YES" << '\n';
  for (auto i : r) {
    cout << i.first << ' ' << i.second << '\n';
  }
}
