#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
vector<int> E[maxn];
int col[maxn], siz[maxn];
int n, m, D, totcol;
bool vis[maxn], firstlayer[maxn];
vector<int> group[maxn];
vector<pair<int, int> > ans;
int color(int x) {
  int ret = 0;
  for (auto v : E[x])
    if (!col[v]) {
      col[v] = col[x];
      ret += color(v);
    }
  return ret;
}
void dfs(int x) {
  vis[x] = 1;
  for (auto v : E[x])
    if (!vis[v]) ans.push_back(make_pair(x, v)), dfs(v);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> D;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  col[1] = -1;
  for (auto v : E[1]) {
    if (!col[v]) {
      col[v] = ++totcol;
      siz[col[v]] = color(v);
    }
    group[col[v]].push_back(v);
    firstlayer[v] = 1;
  }
  if (totcol > D || E[1].size() < D) {
    cout << "NO" << endl;
    return 0;
  }
  cout << "YES" << endl;
  D -= totcol;
  vis[1] = 1;
  for (int i = 1; i <= totcol; ++i) {
    int ch = min(D, int(group[i].size() - 1));
    D -= ch;
    ans.clear();
    dfs(group[i][0]);
    cout << 1 << ' ' << group[i][0] << endl;
    for (auto v : ans) {
      if (ch && firstlayer[v.second])
        --ch, cout << 1 << ' ' << v.second << endl;
      else
        cout << v.first << ' ' << v.second << endl;
    }
  }
  return 0;
}
