#include <bits/stdc++.h>
using namespace std;
void err(istream_iterator<string> it) {}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << "\n";
  err(++it, args...);
}
const double PI = acos(-1);
const double eps = (1e-9);
const long long int INF = 2e9;
const int N = (2e5) + 5;
vector<int> ad;
vector<pair<int, int> > edge;
int par[N], lev[N], tot[N];
void makeset(int n) {
  fill(par, par + n, -1);
  fill(lev, lev + n, 0);
  fill(tot, tot + n, 1);
  return;
}
int findset(int x) {
  int y = x;
  while (par[y] >= 0) y = par[y];
  if (x != y) par[x] = y;
  return y;
}
int combine(int a, int b) {
  a = findset(a);
  b = findset(b);
  if (a != b) {
    if (lev[a] > lev[b]) swap(a, b);
    par[a] = b, tot[b] += tot[a];
    if (lev[a] == lev[b]) lev[b]++;
    return 1;
  }
  return 0;
}
void solve() {
  int n, m, d, a, b;
  scanf("%d%d%d", &n, &m, &d);
  while (m--) {
    scanf("%d%d", &a, &b);
    if (a > b) swap(a, b);
    if (a == 1)
      ad.emplace_back(b);
    else
      edge.emplace_back(a, b);
  }
  if (d > (int)ad.size()) printf("NO\n"), exit(0);
  n++;
  makeset(n);
  for (auto temp : edge) {
    tie(a, b) = temp;
    combine(a, b);
  }
  set<int> ans;
  for (auto a : ad)
    if (combine(1, a)) ans.insert(a);
  if ((int)ans.size() > d) printf("NO\n"), exit(0);
  makeset(n);
  vector<pair<int, int> > ar;
  for (auto a : ad) {
    if (ans.count(a))
      combine(1, a), ar.emplace_back(1, a);
    else if ((int)ans.size() < d)
      combine(1, a), ans.insert(a), ar.emplace_back(1, a);
  }
  for (auto temp : edge) {
    tie(a, b) = temp;
    if (combine(a, b)) ar.emplace_back(a, b);
  }
  printf("YES\n");
  for (auto temp : ar) printf("%d %d\n", temp.first, temp.second);
}
int main() {
  int t = 1;
  while (t--) solve();
}
