#include <bits/stdc++.h>
using namespace std;
long long int n, m, d, i, j, k;
vector<vector<long long int>> adj;
vector<bool> vis;
vector<long long int> par, parent;
map<pair<long long int, long long int>, bool> ans;
void DFS1(long long int node, long long int pr, long long int sup) {
  if (vis[node]) return;
  vis[node] = true;
  par[node] = pr;
  parent[node] = sup;
  for (auto nei : adj[node]) DFS1(nei, pr, node);
}
void DFS2(long long int node) {
  for (auto nei : adj[node]) {
    if (vis[nei]) continue;
    vis[nei] = true;
    ans[{min(nei, node), max(nei, node)}] = true;
    DFS2(nei);
  }
}
int main() {
  ios_base ::sync_with_stdio(false);
  ;
  cin.tie(NULL);
  ;
  long long int t = 1;
  while (t--) {
    cin >> n >> m >> d;
    adj.resize(n + 1);
    vis.resize(n + 1, false);
    par.resize(n + 1, -1);
    parent.resize(n + 1, 0);
    for (i = 0; i < m; i++) {
      cin >> j >> k;
      adj[j].push_back(k);
      adj[k].push_back(j);
    }
    par[1] = 1;
    if (adj[1].size() < d) {
      cout << "NO";
      return 0;
    }
    map<long long int, bool> mp;
    vis[1] = true;
    for (auto nei : adj[1]) {
      mp[nei] = true;
      DFS1(nei, nei, 0);
    }
    map<long long int, bool> used;
    for (i = 2; i <= n; i++) {
      if (par[i] == -1) continue;
      ans[{1, par[i]}] = true;
      used[par[i]] = true;
    }
    k = ans.size();
    if (ans.size() > d) {
      cout << "NO";
      return 0;
    }
    for (i = 1; i <= n; i++) vis[i] = false;
    vis[1] = true;
    for (auto x : used) {
      long long int nei = x.first;
      vis[nei] = true;
      DFS2(nei);
    }
    for (auto x : used) mp.erase(x.first);
    used.clear();
    while (k != d) {
      long long int node = mp.begin()->first;
      ans[{1, node}] = true;
      k++;
      mp.erase(node);
      ans.erase({min(node, parent[node]), max(node, parent[node])});
    }
    cout << "YES"
         << "\n";
    for (auto x : ans) cout << x.first.first << " " << x.first.second << "\n";
  }
}
