#include <bits/stdc++.h>
using namespace std;
const int inf = 2100000000;
struct Ufind {
  map<int, int> node;
  void addN(int ind) {
    if (node[ind] == 0) node[ind] = ind;
  }
  int endN(int n) {
    if (node[n] == n) return n;
    node[n] = endN(node[n]);
    return node[n];
  }
  void joinN(int n1, int n2) { node[endN(n1)] = endN(n2); }
} UF, seg;
void solve() {
  int n, m, d, tmp1, tmp2;
  cin >> n >> m >> d;
  vector<pair<int, int>> edgeL;
  vector<pair<int, int>> edgeL1;
  for (int i = 0; i < (n); i++) {
    UF.addN(i + 1);
    seg.addN(i + 1);
  }
  for (int i = 0; i < (m); i++) {
    cin >> tmp1 >> tmp2;
    if (tmp1 == 1 || tmp2 == 1) {
      edgeL1.push_back(tmp1 < tmp2 ? make_pair(tmp1, tmp2)
                                   : make_pair(tmp2, tmp1));
    } else {
      edgeL.push_back(tmp1 < tmp2 ? make_pair(tmp1, tmp2)
                                  : make_pair(tmp2, tmp1));
    }
  }
  if (edgeL1.size() < d) {
    cout << "NO" << endl;
    return;
  }
  for (int i = 0; i < (edgeL.size()); i++) {
    if (seg.endN(edgeL[i].first) != seg.endN(edgeL[i].second)) {
      seg.joinN(edgeL[i].first, edgeL[i].second);
    }
  }
  map<int, bool> seen;
  int numSeen = 0;
  for (int i = 2; i <= n; i++) {
    if (seen[seg.endN(i)] == false) {
      seen[seg.endN(i)] = true;
      numSeen++;
    }
  }
  if (numSeen > d) {
    cout << "NO" << endl;
    return;
  }
  cout << "YES" << endl;
  int edge1Used = 0;
  for (int i = 0; i < (edgeL1.size()); i++) {
    if (seen[seg.endN(edgeL1[i].second)] == 1) {
      seen[seg.endN(edgeL1[i].second)] = 0;
      UF.joinN(edgeL1[i].first, edgeL1[i].second);
      cout << edgeL1[i].first << ' ' << edgeL1[i].second << endl;
      edgeL1[i] = make_pair(0, 0);
      edge1Used++;
    }
  }
  for (int i = 0; i < (edgeL1.size()); i++) {
    if (edge1Used >= d) break;
    if (edgeL1[i].first != 0) {
      UF.joinN(edgeL1[i].first, edgeL1[i].second);
      cout << edgeL1[i].first << ' ' << edgeL1[i].second << endl;
      edge1Used++;
    }
  }
  for (int i = 0; i < (edgeL.size()); i++) {
    if (UF.endN(edgeL[i].first) != UF.endN(edgeL[i].second)) {
      UF.joinN(edgeL[i].first, edgeL[i].second);
      cout << edgeL[i].first << ' ' << edgeL[i].second << endl;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  solve();
}
