#include <bits/stdc++.h>
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c *x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  ~debug() { cerr << endl; }
  template <class c>
  typename enable_if<sizeof dud<c>(0) != 1, debug &>::type operator<<(c i) {
    cerr << boolalpha << i;
    return *this;
  }
  template <class c>
  typename enable_if<sizeof dud<c>(0) == 1, debug &>::type operator<<(c i) {
    return *this << range(begin(i), end(i));
  }
  template <class c, class b>
  debug &operator<<(pair<b, c> d) {
    return *this << "(" << d.first << ", " << d.second << ")";
  }
  template <class c>
  debug &operator<<(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it;
    return *this << "]";
  }
};
class dsu {
 public:
  vector<int> p;
  int n;
  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }
  inline int get(int x) { return (x == p[x] ? x : (p[x] = get(p[x]))); }
  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};
vector<int> adj[100001];
map<pair<int, int>, int> have;
int n;
int m;
void solve() {
  cin >> n >> m;
  dsu d(n + 1);
  int k;
  cin >> k;
  dsu final(n + 1);
  vector<pair<int, int>> edges;
  map<int, int> withone;
  int deg = 0;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    if (a > 1 && b > 1) {
      edges.push_back({a, b});
      d.unite(a, b);
    }
    if (a == 1 || b == 1) deg++;
    if (a == 1) withone[b] = 1;
    if (b == 1) withone[a] = 1;
  }
  int cc = 0;
  for (int i = 2; i <= n; i++) {
    if (d.get(i) == i) cc++;
  }
  if (cc > k || k > deg) {
    cout << "NO" << endl;
    return;
  }
  int count = 0;
  map<int, int> compdone;
  for (int i = 2; i <= n; i++) {
    int node = d.get(i);
    if (compdone[node] == 0 && withone[i]) {
      compdone[node] = 1;
      withone[i] = 0;
      have[{i, 1}];
      final.unite(i, 1);
      count++;
    }
  }
  int left = k - count;
  if (left != 0) {
    for (int i = 2; i <= n; i++) {
      int a = i;
      if (withone[a] && left > 0) {
        final.unite(a, 1);
        have[{i, 1}];
        left--;
        if (left == 0) goto end;
      }
    }
  }
end:
  assert(left == 0);
  for (auto it : edges) {
    if (final.unite(it.first, it.second)) have[{it.first, it.second}];
  }
  cout << "YES" << endl;
  for (auto it : have) {
    cout << it.first.second << " " << it.first.first << endl;
  }
}
int main() {
  int t = 1;
  while (t--) solve();
  return 0;
}
