#include <bits/stdc++.h>
using namespace std;
bool comp(long long a, long long b) {
  if (a > b)
    return true;
  else
    return false;
}
int isP(long long n) {
  if (n == 1) return 0;
  if (n == 2 || n == 3) return 1;
  for (long long i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) return 0;
  }
  return 1;
}
vector<long long> g[200001];
vector<pair<long long, long long> > ans;
bool vis[200001];
void fun(long long src) {
  vis[src] = true;
  for (long long i = 0; i < g[src].size(); i++) {
    if (!vis[g[src][i]]) {
      ans.push_back(make_pair(src, g[src][i]));
      fun(g[src][i]);
    }
  }
}
map<long long, long long> is;
long long d, conn;
long long diff;
void fun2(long long src) {
  vis[src] = true;
  for (long long i = 0; i < g[src].size(); i++) {
    if (!vis[g[src][i]]) {
      if (is[g[src][i]] && diff) {
        diff--;
        ans.push_back(make_pair(1, g[src][i]));
        fun2(g[src][i]);
      } else {
        ans.push_back(make_pair(src, g[src][i]));
        fun2(g[src][i]);
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long n, m, i, u, v, in, cnt1 = 0;
  cin >> n >> m >> d;
  for (i = 1; i <= m; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
    if (u == 1 || v == 1) cnt1++;
  }
  if (cnt1 < d) {
    cout << "NO" << endl;
    return 0;
  }
  if (cnt1 == d) {
    vis[1] = true;
    for (i = 0; i < g[1].size(); i++) {
      ans.push_back(make_pair(1, g[1][i]));
      vis[g[1][i]] = true;
    }
    for (i = 0; i < g[1].size(); i++) {
      fun(g[1][i]);
    }
    cout << "YES" << endl;
    for (i = 0; i < ans.size(); i++) {
      cout << ans[i].first << " " << ans[i].second << endl;
    }
    return 0;
  }
  vis[1] = true;
  for (i = 0; i < g[1].size(); i++) {
    if (!vis[g[1][i]]) {
      conn++;
      fun(g[1][i]);
    }
  }
  if (conn > d) {
    cout << "NO" << endl;
    return 0;
  }
  memset(vis, false, sizeof(vis));
  ans.clear();
  for (i = 0; i < g[1].size(); i++) {
    is[g[1][i]]++;
  }
  diff = d - conn;
  vis[1] = true;
  for (i = 0; i < g[1].size(); i++) {
    if (!vis[g[1][i]]) {
      ans.push_back(make_pair(1, g[1][i]));
      fun2(g[1][i]);
    }
  }
  cout << "YES" << endl;
  for (i = 0; i < ans.size(); i++) {
    cout << ans[i].first << " " << ans[i].second << endl;
  }
  return 0;
}
