#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 4;
vector<int> par(N, 0);
int find(int x) {
  if (par[x] == x) return x;
  return par[x] = find(par[x]);
}
int solve() {
  int n, m, k;
  scanf("%d", &n);
  scanf("%d", &m);
  scanf("%d", &k);
  iota(par.begin(), par.end(), 0);
  vector<int> deg(n + 1, 0);
  vector<pair<int, int>> edges;
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d", &a);
    scanf("%d", &b);
    deg[a]++;
    deg[b]++;
    edges.emplace_back(a, b);
  }
  if (deg[1] < k or k == 0) {
    printf("NO");
    return 0;
  }
  set<pair<int, int>> ans;
  int components = n;
  for (int i = 0; i < m; i++) {
    int x = edges[i].first, y = edges[i].second;
    if (x == 1 or y == 1) continue;
    int px = find(x), py = find(y);
    if (px != py) ans.emplace(x, y), par[px] = py, components--;
  }
  set<int> parents;
  if (components - k > 1) {
    printf("NO");
    return 0;
  }
  printf("YES\n");
  for (int i = 1; i < n + 1; i++) parents.insert(find(i));
  vector<pair<int, int>> va;
  vector<int> marked(n + 1, 0);
  set<int> used;
  int ok = k;
  vector<int> pari(n + 1, 0);
  iota(pari.begin(), pari.end(), 0);
  for (int i = 0; i < m; i++)
    if (k > 0) {
      int x = edges[i].first, y = edges[i].second;
      if (x == 1 or y == 1) {
        if (x != 1) swap(x, y);
        int px = find(x), py = find(y);
        if (parents.find(py) != parents.end())
          used.insert(y), marked[y] = 1, parents.erase(py), k--,
                          va.emplace_back(x, y), pari[y] = x;
      }
    }
  for (int i = 1; i < n + 1; i++) par[i] = pari[i];
  for (int i = 0; i < m; i++)
    if (k > 0) {
      int x = edges[i].first, y = edges[i].second;
      if (x == 1 or y == 1) {
        if (x != 1) swap(x, y);
        if (marked[y]) continue;
        int px = find(x), py = find(y);
        used.insert(y);
        va.emplace_back(x, y), k--, par[px] = py;
      }
    }
  for (auto it : ans) {
    int x = it.first, y = it.second;
    int px = find(x), py = find(y);
    if (px != py) va.emplace_back(x, y), par[px] = py;
  }
  assert((int)used.size() == ok);
  if ((int)va.size() != n - 1) cout << (int)va.size() << endl;
  for (auto it : va) printf("%d %d\n", it.first, it.second);
  return 0;
}
int main() {
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
