#include <bits/stdc++.h>
using namespace std;
long long MOD = 1e9 + 7;
inline long long nxt() {
  long long x;
  scanf("%d", &x);
  return x;
}
long long st(long long t, long long id, long long mod) {
  long long res = 1, a = t, n = id;
  while (n) {
    if (n & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    n >>= 1;
  }
  return res % mod;
}
long long del(long long a, long long b) {
  return (a * st(b, MOD - 2, MOD)) % MOD;
}
const int NN = 1000000;
vector<long long> gr[NN];
vector<long long> g[NN];
long long p[NN];
long long used[NN];
long long used2[NN];
void dfs(long long v) {
  used[v] = 1;
  for (auto i : gr[v]) {
    if (!used[i]) {
      g[v].push_back(i);
      g[i].push_back(v);
      dfs(i);
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, m, D;
  cin >> n >> m >> D;
  for (int i = 0; i < m; i++) {
    long long u, v;
    cin >> u >> v;
    u--, v--;
    gr[u].push_back(v);
    gr[v].push_back(u);
  }
  dfs(0);
  if (g[0].size() > D) {
    cout << "NO";
    return 0;
  }
  set<long long> mem;
  for (auto i : g[0]) {
    mem.insert(i);
  }
  for (auto i : gr[0]) {
    if (!mem.count(i) && g[0].size() < D) {
      g[0].push_back(i);
      g[i].push_back(0);
    }
  }
  if (g[0].size() < D) {
    cout << "NO";
    return 0;
  }
  queue<long long> q;
  q.push(0);
  used2[0] = 1;
  cout << "YES" << endl;
  while (q.size()) {
    long long v = q.front();
    q.pop();
    for (auto i : g[v]) {
      if (!used2[i]) {
        used2[i] = 1;
        cout << v + 1 << " " << i + 1 << endl;
        q.push(i);
      }
    }
  }
}
