#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> edges;
int parent[1000000] = {0};
int S[1000000] = {0};
unordered_map<int, vector<int>> nodes, tree;
int Find(int x) {
  while (parent[x] != x) {
    parent[x] = parent[parent[x]];
    x = parent[x];
  }
  return x;
}
void Union(int x, int y) {
  x = Find(x);
  y = Find(y);
  if (x == y) return;
  if (S[x] < S[y]) {
    S[y] += S[x];
    parent[x] = y;
    return;
  }
  S[x] += S[y];
  parent[y] = x;
}
int main() {
  int n, m, D;
  cin >> n >> m >> D;
  for (int i = 0; i <= n; i++) {
    parent[i] = i;
    S[i] = 1;
  }
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    nodes[x].push_back(y);
    nodes[y].push_back(x);
    if ((x == 1) || (y == 1)) continue;
    edges.push_back(make_pair(x, y));
  }
  if (nodes[1].size() < D) {
    cout << "NO\n";
    return 0;
  }
  for (int i = 0; i < edges.size(); i++) {
    int x = edges[i].first;
    int y = edges[i].second;
    Union(x, y);
  }
  set<int> inp;
  for (int i = 0; i < nodes[1].size(); i++) {
    if (Find(nodes[1][i]) != Find(1)) {
      Union(nodes[1][i], 1);
      inp.insert(nodes[1][i]);
    }
  }
  if (inp.size() > D) {
    cout << "NO\n";
    return 0;
  }
  cout << "YES\n";
  for (int i = 0; i <= n; i++) {
    parent[i] = i;
    S[i] = 1;
  }
  vector<pair<int, int>> X;
  for (auto i : inp) {
    X.push_back(make_pair(1, i));
    Union(1, i);
  }
  for (int i = 0; i < nodes[1].size(); i++) {
    if (X.size() == D) break;
    if (inp.count(nodes[1][i]) == 0) {
      X.push_back(make_pair(1, nodes[1][i]));
      Union(1, nodes[1][i]);
    }
  }
  for (int i = 0; i < edges.size(); i++) {
    int x = edges[i].first;
    int y = edges[i].second;
    if (Find(x) != Find(y)) {
      X.push_back(make_pair(x, y));
      Union(x, y);
    }
  }
  assert((X.size() == n - 1));
  for (int i = 0; i < X.size(); i++) {
    cout << X[i].first << ' ' << X[i].second << '\n';
  }
  return 0;
}
