#include <bits/stdc++.h>
using namespace std;
const int N = 1000 * 1000 + 20;
int n, m, d, deg[N], par[N];
vector<int> vec, adj[N];
vector<pair<int, int>> ans;
queue<int> Q;
int get_par(int v) { return par[v] == v ? v : par[v] = get_par(par[v]); }
void Union(int v, int u) {
  v = get_par(v), u = get_par(u);
  if (v == u) return;
  par[u] = v;
}
void BFS() {
  for (int i = 2; i <= n; i++) Q.push(i);
  while (!Q.empty()) {
    int v = Q.front();
    Q.pop();
    for (auto u : adj[v])
      if (u ^ 1)
        if (get_par(v) ^ get_par(u)) Union(v, u);
  }
}
void BFS1() {
  while (!Q.empty()) {
    int v = Q.front();
    Q.pop();
    for (auto u : adj[v])
      if (u ^ 1)
        if (get_par(v) ^ get_par(u)) {
          ans.push_back(make_pair(u, v));
          Union(v, u);
          Q.push(u);
        }
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  cin >> n >> m >> d;
  for (int i = 1; i <= n; i++) par[i] = i;
  for (int i = 0, v, u; i < m; i++) {
    cin >> v >> u;
    adj[v].push_back(u);
    adj[u].push_back(v);
    deg[v]++, deg[u]++;
  }
  if (deg[1] < d) return cout << "NO" << endl, 0;
  BFS();
  for (auto u : adj[1])
    if (get_par(1) ^ get_par(u)) {
      vec.push_back(u);
      Union(1, u);
    }
  if ((int)vec.size() > d) return cout << "NO" << endl, 0;
  for (int i = 1; i <= n; i++) par[i] = i;
  for (auto x : vec)
    if (get_par(1) ^ get_par(x)) {
      Union(1, x);
      ans.push_back(make_pair(1, x));
      Q.push(x);
    }
  int ind = 0, cnt = d - vec.size();
  while (cnt) {
    if (get_par(1) ^ get_par(adj[1][ind])) {
      Q.push(adj[1][ind]);
      ans.push_back(make_pair(1, adj[1][ind]));
      Union(1, adj[1][ind]);
      cnt--;
    }
    ind++;
  }
  BFS1();
  cout << "YES" << endl;
  for (auto [v, u] : ans) cout << v << " " << u << endl;
  return 0;
}
