#include <bits/stdc++.h>
using namespace std;
struct Union_Find {
  vector<int> rank, par;
  int independent_tree;
  int N;
  Union_Find() = default;
  Union_Find(int n) {
    N = n;
    for (int i = 0; i < N; i++) rank.push_back(1), par.push_back(i);
    independent_tree = N;
  }
  void setsize(int n) {
    N = n;
    for (int i = 0; i < N; i++) rank.push_back(1), par.push_back(i);
    independent_tree = N;
  }
  int getroot(int X) {
    if (par[X] == X) return X;
    return par[X] = getroot(par[X]);
  }
  bool issame(int A, int B) { return getroot(A) == getroot(B); }
  void unite(int A, int B) {
    A = getroot(A), B = getroot(B);
    if (A == B) return;
    independent_tree--;
    if (rank[A] > rank[B]) {
      par[B] = A;
    } else if (rank[A] == rank[B]) {
      par[B] = A;
      rank[A]++;
    } else {
      par[A] = B;
    }
  }
};
int n, m, D;
vector<vector<int>> E;
int dig[200000 + 100];
bool visited[200000 + 100];
void dfs(int now, int bef, vector<int>& to0) {
  visited[now] = true;
  for (int i = 0; i < E[now].size(); i++) {
    int nxt = E[now][i];
    if (nxt == bef) continue;
    if (!visited[nxt]) {
      dfs(nxt, now, to0);
    }
    if (nxt == 0) {
      to0.push_back(now);
    }
  }
}
int main() {
  cin >> n >> m >> D;
  E.resize(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    E[u].push_back(v);
    E[v].push_back(u);
    dig[u]++, dig[v]++;
  }
  vector<vector<int>> from_0;
  visited[0] = true;
  for (int i = 0; i < E[0].size(); i++) {
    int nxt = E[0][i];
    if (!visited[nxt]) {
      vector<int> tmp;
      tmp.push_back(nxt);
      dfs(nxt, 0, tmp);
      from_0.push_back(tmp);
    }
  }
  if (D > dig[0] || D < from_0.size()) {
    cout << "NO" << endl;
    return 0;
  }
  D -= from_0.size();
  queue<int> pos;
  vector<pair<int, int>> ans;
  Union_Find uf(n + 100);
  for (int i = 0; i < from_0.size(); i++) {
    ans.push_back(make_pair(0, from_0[i][0]));
    pos.push(from_0[i][0]);
    uf.unite(0, from_0[i][0]);
    for (int j = 1; j < from_0[i].size() && D > 0; j++, D--) {
      ans.push_back(make_pair(0, from_0[i][j]));
      pos.push(from_0[i][j]);
      uf.unite(0, from_0[i][j]);
    }
  }
  while (pos.size()) {
    int now = pos.front();
    pos.pop();
    for (int i = 0; i < E[now].size(); i++) {
      int nxt = E[now][i];
      if (!uf.issame(now, nxt)) {
        pos.push(nxt);
        ans.push_back(make_pair(now, nxt));
        uf.unite(now, nxt);
      }
    }
  }
  cout << "YES" << endl;
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl;
  }
  return 0;
}
