#include <bits/stdc++.h>
using namespace std;
const long long maxn = 2e5 + 4;
int n, m, D;
vector<pair<int, int> > edge, ans, edge1;
vector<int> adj, p;
int get(int ind) {
  if (p[ind] == ind) return ind;
  return get(p[ind]);
}
void merge(int a, int b) {
  int p1 = get(a);
  int p2 = get(b);
  if (p1 > p2) swap(p1, p2);
  p[p2] = p1;
}
void kruskal(int cond) {
  ans.clear();
  int counter = 0;
  for (auto it : edge) {
    int a = it.first, b = it.second;
    if (cond == 1 && (a == 0 || b == 0)) continue;
    if (get(a) != get(b)) {
      merge(a, b);
      counter++;
      ans.push_back(it);
    }
  }
}
int main() {
  cin >> n >> m >> D;
  p.resize(n);
  for (int(i) = 0; (i) < (m); (i)++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    edge.push_back(make_pair(a, b));
    if (a == 0) adj.push_back(b);
    if (b == 0) adj.push_back(a);
  }
  for (int(i) = 0; (i) < (n); (i)++) p[i] = i;
  kruskal(1);
  vector<int> acc(adj.size(), 0);
  int c = 0;
  for (auto it : adj) {
    if (get(0) != get(it)) {
      merge(0, it);
      edge1.push_back(make_pair(0, it));
      acc[c] = 1;
    }
    c++;
  }
  if (D > adj.size() || D < edge1.size()) {
    cout << "NO" << endl;
    return 0;
  }
  int req = D - edge1.size();
  for (int(i) = 0; (i) < (adj.size()); (i)++) {
    if (req == 0) break;
    if (acc[i] == 0) {
      edge1.push_back(make_pair(0, adj[i]));
      req--;
    }
  }
  for (int(i) = 0; (i) < (n); (i)++) p[i] = i;
  for (auto it : edge1) {
    merge(it.first, it.second);
  }
  kruskal(1);
  cout << "YES" << endl;
  for (auto it : edge1) cout << it.first + 1 << " " << it.second + 1 << endl;
  for (auto it : ans) cout << it.first + 1 << " " << it.second + 1 << endl;
}
