#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
vector<int> tut, ed[N];
vector<pair<int, int> > vec, ans;
int mx, n, m, k, op[N], dad[N], sz[N], mark[N];
int find(int u) {
  if (dad[u] == u) return u;
  return dad[u] = find(dad[u]);
}
inline void merge(int u, int v) { dad[find(u)] = find(v); }
inline void merge2(int u, int v) {
  int du = find(u);
  int dv = find(v);
  if (du == dv) return;
  sz[du] = max(sz[du], sz[dv]);
  dad[dv] = du;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) dad[i] = i;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    if (u == 1) op[v] = 1;
    if (v == 1) op[u] = 1;
    ed[u].push_back(v);
    ed[v].push_back(u);
    vec.push_back({u, v});
  }
  for (int i = 1; i <= n; i++)
    if (op[i]) sz[i] = i;
  for (auto i : vec) {
    int u = i.first;
    int v = i.second;
    if (min(u, v) == 1) continue;
    merge2(u, v);
  }
  for (int i = 1; i <= n; i++) mark[i] = sz[find(i)];
  for (int i = 1; i <= n; i++) dad[i] = i;
  for (auto i : ed[1]) {
    if (mark[i] != i) continue;
    k--;
    merge(1, i);
    ans.push_back({1, i});
  }
  if (k < 0) {
    cout << "NO\n";
    return 0;
  }
  for (auto i : ed[1]) {
    if (mark[i] == i || k == 0) continue;
    k--;
    ans.push_back({1, i});
    merge(1, i);
  }
  if (k != 0) {
    cout << "NO\n";
    return 0;
  }
  for (auto i : vec) {
    int u = i.first;
    int v = i.second;
    if (min(u, v) == 1 || find(u) == find(v)) continue;
    ans.push_back({u, v});
    merge(u, v);
  }
  for (int i = 1; i <= n; i++) {
    if (find(i) != find(1)) {
      cout << "NO\n";
      return 0;
    }
  }
  cout << "YES\n";
  for (auto i : ans) cout << i.first << " " << i.second << "\n";
}
