#include <bits/stdc++.h>
const int N = 1e6;
using namespace std;
int n, m, k, p[N], chosen[N], check[N];
vector<int> g[N];
int root(int u) { return ((p[u] < 0) ? u : p[u] = root(p[u])); }
void unite(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) return;
  if (p[u] < p[v]) swap(u, v);
  p[u] += p[v];
  p[v] = u;
}
void solve() {
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) p[i] = -1;
  for (int i = 2; i <= n; i++)
    for (int v : g[i])
      if (v != 1) unite(i, v);
  int cnt = 0;
  for (int i = 2; i <= n; i++) cnt += (p[i] < 0);
  if (cnt > k) {
    cout << "NO" << endl;
    return;
  }
  cnt = 0;
  vector<pair<int, int>> res;
  for (int u : g[1])
    if (!chosen[u]) {
      int v = root(u);
      if (!check[v]) {
        check[v] = 1;
        chosen[u] = 1;
        cnt++;
        res.push_back({1, u});
      }
    }
  for (int u : g[1]) {
    if (cnt == k) break;
    if (!chosen[u]) {
      chosen[u] = 1;
      res.push_back({1, u});
      cnt++;
    }
  }
  if (cnt < k) {
    cout << "NO" << endl;
    return;
  }
  for (int i = 1; i <= n; i++) p[i] = -1;
  cout << "YES" << endl;
  for (int i = 0; i < res.size(); i++) {
    int u = res[i].first, v = res[i].second;
    cout << u << " " << v << endl;
    unite(u, v);
  }
  for (int i = 2; i <= n; i++)
    for (int u : g[i])
      if (u != 1) {
        if (root(i) == root(u)) continue;
        cout << i << " " << u << endl;
        unite(i, u);
      }
}
int main() {
  solve();
  return 0;
}
