#include <bits/stdc++.h>
using LL = long long;
using D = double;
using namespace std;
const int N = 2e5 + 1;
vector<int> G[N];
int C[N];
void dfs(int v, int c) {
  C[v] = c;
  for (auto to : G[v]) {
    if (C[to] != -1) continue;
    dfs(to, c);
  }
}
int main() {
  ios::sync_with_stdio(false);
  int n, m, d;
  cin >> n >> m >> d;
  vector<int> F;
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    if (u == 1)
      F.push_back(v);
    else if (v == 1)
      F.push_back(u);
    else {
      G[u].push_back(v);
      G[v].push_back(u);
    }
  }
  if (F.size() < d) {
    cout << "NO";
    return 0;
  }
  memset(C, -1, sizeof(C));
  vector<int> a[F.size()];
  int c = 0;
  for (auto to : F) {
    if (C[to] == -1) {
      dfs(to, c);
      c++;
    }
    a[C[to]].push_back(to);
  }
  if (c > d) {
    cout << "NO";
    return 0;
  }
  vector<int> H;
  for (int i = 0; i < c; ++i) {
    H.push_back(a[i].back());
    a[i].pop_back();
    d--;
  }
  int p = 0;
  while (d > 0) {
    while (d > 0 && a[p].size() > 0) {
      H.push_back(a[p].back());
      a[p].pop_back();
      d--;
    }
    p++;
  }
  vector<pair<int, int>> res;
  int q[n], used[n + 1], l = 0, r = 0;
  memset(used, 0, sizeof(used));
  used[1] = 1;
  for (auto to : H) {
    used[to] = 1;
    q[r++] = to;
    res.push_back({1, to});
  }
  while (l < r) {
    int v = q[l++];
    for (auto to : G[v]) {
      if (used[to]) continue;
      used[to] = 1;
      q[r++] = to;
      res.push_back({v, to});
    }
  }
  cout << "YES\n";
  for (auto [v, u] : res) cout << v << ' ' << u << '\n';
}
