#include <bits/stdc++.h>
using namespace std;
void output(int u, int v) { cout << u << " " << v << endl; }
class DSU {
 public:
  vector<int> parents;
  vector<int> sizes;
  DSU(int n) {
    parents.resize(n + 1);
    for (int i = 1; i <= n; ++i) parents[i] = i;
    sizes.resize(n + 1);
    for (int i = 1; i <= n; ++i) sizes[i] = 1;
  }
  int root(int i) {
    while (parents[i] != i) {
      parents[i] = parents[parents[i]];
      i = parents[i];
    }
    return i;
  }
  bool find(int a, int b) { return root(a) == root(b); }
  void join(int a, int b) {
    int root_a = root(a);
    int root_b = root(b);
    if (sizes[root_a] < sizes[root_b]) {
      parents[root_a] = parents[root_b];
      sizes[root_b] += sizes[root_a];
    } else {
      parents[root_b] = parents[root_a];
      sizes[root_a] += sizes[root_b];
    }
  }
  int num_comps() {
    int n = parents.size() - 1;
    set<int> comps;
    for (int i = 2; i <= n; ++i) {
      comps.insert(root(i));
    }
    return comps.size();
  }
};
void dfs(int parent, int index, vector<vector<int>>& edges,
         vector<bool>& seen) {
  output(parent, index);
  seen[index] = true;
  for (int edge : edges[index]) {
    if (!seen[edge]) dfs(index, edge, edges, seen);
  }
}
int32_t main() {
  int n, m, d;
  cin >> n >> m >> d;
  vector<vector<int>> edges(n + 1, vector<int>());
  DSU dsu(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    edges[u].push_back(v);
    edges[v].push_back(u);
    if (u != 1 && v != 1) {
      dsu.join(u, v);
    }
  }
  int nc = dsu.num_comps();
  if (d > (int)edges[1].size() || d < nc) {
    cout << "NO" << endl;
    return 0;
  }
  cout << "YES" << endl;
  int extra = d - nc;
  vector<bool> seen(n + 1, false);
  seen[1] = true;
  unordered_set<int> roots;
  vector<int> start;
  for (int edge : edges[1]) {
    int root = dsu.root(edge);
    if (roots.find(root) == roots.end()) {
      roots.insert(root);
      seen[edge] = true;
      start.push_back(edge);
    } else if (extra > 0) {
      extra--;
      seen[edge] = true;
      start.push_back(edge);
    }
  }
  for (int st : start) {
    dfs(1, st, edges, seen);
  }
  return 0;
}
