#include <bits/stdc++.h>
using namespace std;
int p[234567];
vector<int> G[234567], G1;
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
void unite(int u, int v) { p[find(u)] = find(v); }
vector<pair<int, int> > ans, edge;
int main() {
  ios::sync_with_stdio();
  cin.tie(0);
  for (int i = 0; i < 234567; i++) p[i] = i;
  int n, m, D;
  cin >> n >> m >> D;
  int in = 0;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    if (u != 1 && v != 1) {
      G[u].push_back(v);
      G[v].push_back(u);
      edge.push_back(make_pair(u, v));
      if (find(u) != find(v)) unite(u, v);
    } else
      G1.push_back(u == 1 ? v : u), in++;
  }
  int cnt1 = 0;
  map<int, bool> mp;
  for (int i = 2; i <= n; i++) {
    int u = find(i);
    if (!mp[u]) cnt1++;
    mp[u] = true;
  }
  mp.clear();
  int cnt2 = 0;
  for (int i = 0; i < G1.size(); i++) {
    int u = find(G1[i]);
    if (!mp[u]) cnt2++;
    mp[u] = true;
  }
  if (D > in || D < cnt1 || cnt1 > cnt2)
    cout << "NO\n";
  else {
    int cnt = 0;
    bool chosen[234567] = {};
    mp.clear();
    for (int i = 0; i < G1.size(); i++) {
      int u = find(G1[i]);
      if (!mp[u]) {
        mp[u] = true;
        chosen[i] = true;
        ++cnt, ans.push_back(make_pair(1, G1[i]));
      }
    }
    for (int i = 0; i < G1.size() && cnt < D; i++) {
      if (!chosen[i]) ++cnt, ans.push_back(make_pair(1, G1[i]));
    }
    for (int i = 0; i <= n; i++) p[i] = i;
    for (int i = 0; i < ans.size(); i++) unite(1, ans[i].second);
    for (int i = 0; i < edge.size(); i++) {
      int u = edge[i].first, v = edge[i].second;
      if (find(u) != find(v)) {
        unite(u, v);
        ans.push_back(edge[i]);
      }
    }
    cout << "YES\n";
    for (int i = 0; i < ans.size(); i++)
      cout << ans[i].first << ' ' << ans[i].second << endl;
  }
}
