#include <bits/stdc++.h>
using namespace std;
int64_t inf = 1000 * 1000 * 1000;
int64_t inf64 = inf * inf;
void dfs(int v, vector<vector<int>> &g, vector<int> &used, int print) {
  used[v] = 1;
  for (int i = 0; i < g[v].size(); ++i) {
    int to = g[v][i];
    if (used[to] == 0) {
      if (print) {
        cout << v + 1 << " " << to + 1 << endl;
        dfs(to, g, used, 1);
      } else
        dfs(to, g, used, 0);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, m, d;
  cin >> n >> m >> d;
  vector<vector<int>> g(n);
  vector<int> used(n, 0);
  vector<pair<int, int>> p;
  vector<pair<int, int>> vers;
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    if (x != 1 && y != 1) {
      g[x - 1].emplace_back(y - 1);
      g[y - 1].emplace_back(x - 1);
    } else {
      if (x == 1)
        vers.emplace_back(y - 1, 0);
      else
        vers.emplace_back(x - 1, 0);
      p.emplace_back(x - 1, y - 1);
    }
  }
  int cs = 0;
  used[0] = 1;
  for (int i = 0; i < vers.size(); ++i) {
    if (used[vers[i].first] == 0) {
      ++cs;
      vers[i].second = 1;
      dfs(vers[i].first, g, used, 0);
    }
  }
  if (cs > d || p.size() < d) {
    cout << "NO";
  } else {
    cout << "YES" << endl;
    vector<int> f;
    used.assign(n, 0);
    for (int i = 0; i < vers.size(); ++i) {
      if (vers[i].second == 1) {
        --d;
        f.emplace_back(vers[i].first);
        used[vers[i].first] = 1;
        cout << 1 << " " << vers[i].first + 1 << endl;
      }
    }
    for (int i = 0; i < vers.size(); ++i) {
      if (vers[i].second == 0 && d > 0) {
        f.emplace_back(vers[i].first);
        used[vers[i].first] = 1;
        cout << 1 << " " << vers[i].first + 1 << endl;
        --d;
      }
    }
    used[0] = 1;
    for (auto c : f) {
      dfs(c, g, used, 1);
    }
  }
}
