#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const int N = 2 * 1e5 + 6;
int col[N];
bool jnj[N], del[N], cl[N];
vector<int> g[N];
void dfs(int v, int cl) {
  if (col[v]) return;
  col[v] = cl;
  for (auto to : g[v]) {
    dfs(to, cl);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  int n, m, k;
  cin >> n >> m >> k;
  for (int i = 0; i < (m); ++i) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  col[1] = 1;
  int ql = 2;
  for (long long i = (2); i <= (n); ++i) {
    if (!col[i]) dfs(i, ql++);
  }
  int deg = g[1].size();
  for (auto tv : g[1]) {
    if (jnj[col[tv]] && deg > k) {
      deg--;
      del[tv] = true;
    } else {
      jnj[col[tv]] = true;
    }
  }
  if (deg != k) {
    cout << "NO" << endl;
    return 0;
  }
  cout << "YES" << endl;
  queue<int> q;
  cl[1] = true;
  for (auto tv : g[1]) {
    if (!del[tv]) {
      cout << 1 << " " << tv << endl;
      cl[tv] = true;
      q.push(tv);
    }
  }
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (auto tv : g[v]) {
      if (cl[tv]) continue;
      cout << v << " " << tv << endl;
      cl[tv] = true;
      q.push(tv);
    }
  }
  return 0;
}
