#include <bits/stdc++.h>
using namespace std;
long long dsu[200015];
bool visited[200015];
vector<long long> minreq, extras;
void pre(void) {}
void dfs_utils(long long n, vector<long long> graph[]) {
  for (long long i : graph[n]) {
    if (!visited[i]) {
      visited[i] = true;
      dfs_utils(i, graph);
    }
  }
}
void dfs(long long s, vector<long long> graph[]) {
  visited[s] = true;
  for (long long i : graph[s]) {
    if (!visited[i]) {
      visited[i] = true;
      minreq.push_back(i);
      dfs_utils(i, graph);
    } else {
      extras.push_back(i);
    }
  }
}
long long find(long long n) {
  vector<long long> arr;
  while (dsu[n] > 0) {
    arr.push_back(n);
    n = dsu[n];
  }
  for (long long i = 0; i < arr.size(); i++) {
    dsu[arr[i]] = n;
  }
  return n;
}
long long connect(long long a, long long b) {
  a = find(a);
  b = find(b);
  if (a != b) {
    dsu[a] = b;
  }
  return b;
}
void solve(void) {
  long long n, m, d;
  cin >> n >> m >> d;
  vector<long long> graph[n + 1];
  long long a, b;
  vector<pair<long long, long long>> edges(m);
  for (long long i = 0; i < m; i++) {
    cin >> a >> b;
    edges[i].first = a;
    edges[i].second = b;
    graph[b].push_back(a);
    graph[a].push_back(b);
  }
  vector<long long> tree[n + 1];
  dfs(1, graph);
  tree[1] = minreq;
  if (d < minreq.size() || d > minreq.size() + extras.size()) {
    cout << "NO\n";
    return;
  }
  cout << "YES\n";
  for (; tree[1].size() < d;) {
    tree[1].push_back(extras.back());
    extras.pop_back();
  }
  for (long long i = 0; i < tree[1].size(); i++) {
    connect(1, tree[1][i]);
  }
  for (long long i = 0; i < m; i++) {
    a = edges[i].first;
    b = edges[i].second;
    if (a == 1 || b == 1) continue;
    if (find(a) != find(b)) {
      connect(a, b);
      tree[a].push_back(b);
    }
  }
  for (long long i = 1; i <= n; i++) {
    for (long long j = 0; j < tree[i].size(); j++) {
      cout << i << ' ' << tree[i][j] << '\n';
    }
  }
}
int32_t main(void) {
  std::ios::sync_with_stdio(0);
  std::cin.tie(NULL);
  std::cout.tie(NULL);
  long long t = 1;
  pre();
  for (long long i = 1; i <= t; i++) {
    solve();
  }
  return 0;
}
