#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> ed[200005];
int mk[200005];
vector<int> ed1[200005];
int pa[200005];
int fin(int i) {
  if (pa[i] == i) return i;
  return pa[i] = fin(pa[i]);
}
void join(int a, int b) {
  int u = fin(a);
  int v = fin(b);
  if (mk[u])
    pa[v] = u;
  else
    pa[u] = v;
}
void solve() {
  cin >> n >> m;
  int d;
  cin >> d;
  int dd = 0;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    ed[u].push_back(v);
    ed[v].push_back(u);
    if (v == 1 || u == 1) dd++;
  }
  if (dd < d) {
    cout << "NO";
    return;
  }
  for (int i = 1; i <= n; i++) pa[i] = i;
  for (int i : ed[1]) mk[i] = 1;
  mk[1] = 1;
  pair<int, int> p[n - 1];
  int e = 0;
  for (int j = 2; j <= n; j++) {
    for (int i : ed[j]) {
      if (i == 1 || fin(i) == fin(j)) continue;
      if (mk[fin(i)] && mk[fin(j)]) {
        {
          ed1[i].push_back(j);
          ed1[j].push_back(i);
        }
        continue;
      }
      if (fin(i) != fin(j)) {
        join(i, j);
        p[e++] = pair<int, int>(i, j);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (dd == d) break;
    for (int j : ed1[i]) {
      if (dd == d) break;
      if (fin(i) != fin(j)) {
        join(i, j);
        dd--;
        p[e++] = pair<int, int>(i, j);
      }
    }
  }
  for (int i : ed[1]) {
    if (fin(i) != fin(1)) {
      join(i, 1);
      p[e++] = pair<int, int>(1, i);
    }
  }
  if (dd != d || e < n - 1) {
    cout << "NO";
    return;
  } else
    cout << "YES\n";
  for (int i = 0; i < n - 1; i++) {
    cout << p[i].first << " " << p[i].second << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t;
  t = 1;
  while (t--) {
    solve();
  }
}
