#include <bits/stdc++.h>
using namespace std;
void io() {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
}
vector<vector<int>> g;
int cnt = 0;
vector<char> used;
vector<int> near;
vector<int> comp;
void dfs(int v) {
  used[v] = true;
  comp[v] = cnt;
  for (auto x : g[v]) {
    if (!used[x] && x) dfs(x);
  }
}
signed main() {
  io();
  int n, m, D;
  cin >> n >> m >> D;
  g.resize(n);
  used.resize(n, false);
  comp.resize(n, 0);
  int in = 0;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    if (u > v) swap(u, v);
    g[v].push_back(u);
    if (u == 0) in++, near.push_back(v);
    g[u].push_back(v);
  }
  for (int i = 1; i < n; i++) {
    if (!used[i]) {
      dfs(i);
      cnt++;
    }
  }
  if (in < D || cnt > D) {
    cout << "NO";
    return 0;
  }
  cout << "YES" << endl;
  int remov = in - D;
  vector<vector<int>> g1(n);
  vector<int> clr(n, 0);
  vector<int> ban(n, 0);
  for (auto x : g[0]) {
    clr[comp[x]]++;
  }
  for (auto x : g[0]) {
    if (remov == 0) break;
    if (clr[comp[x]] > 1) {
      remov--;
      clr[comp[x]]--;
      ban[x] = true;
    }
  }
  for (int i = 0; i < n; i++) {
    for (auto x : g[i]) {
      if (!(i == 0 && ban[x] || x == 0 && ban[i])) g1[i].push_back(x);
    }
  }
  queue<int> q;
  used.clear();
  used.resize(n, false);
  q.push(0);
  used[0] = true;
  while (!q.empty()) {
    auto v = q.front();
    q.pop();
    for (auto x : g1[v]) {
      if (!used[x]) {
        cout << v + 1 << ' ' << x + 1 << endl;
        q.push(x);
        used[x] = true;
      }
    }
  }
  return 0;
}
