#include <bits/stdc++.h>
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
using namespace std;
int fa[N], cnt = 0, n, m, d;
long long ans = 0;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void init(int nn) {
  for (int i = 0; i <= nn; i++) fa[i] = i;
}
int deg[N];
int head[N], to[N * 2], nx[N * 2];
int tot = 0;
void add(int u, int v) {
  to[tot] = v;
  nx[tot] = head[u];
  head[u] = tot++;
}
bool vis[N];
void dfs(int u) {
  vis[u] = 1;
  for (int i = head[u]; ~i; i = nx[i]) {
    int v = to[i];
    if (vis[v]) continue;
    dfs(v);
  }
}
bool op[N];
pair<int, int> p[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> d;
  memset(head, -1, sizeof(head));
  init(n);
  int t = 0;
  for (int i = 1; i <= m; ++i) {
    cin >> p[i].first >> p[i].second, deg[p[i].first]++, deg[p[i].second]++;
    add(p[i].first, p[i].second);
    add(p[i].second, p[i].first);
  }
  if (deg[1] < d) return cout << "NO", 0;
  memset(deg, 0, sizeof(deg));
  vector<int> vec;
  int pp = 0;
  vis[1] = 1;
  for (int i = head[1]; ~i; i = nx[i]) {
    int vv = to[i];
    if (!vis[vv]) {
      dfs(vv), vec.push_back(vv);
      int u = find(1), v = find(vv);
      if (u != v) {
        fa[u] = v;
        pp++;
      }
    }
  }
  if ((int)vec.size() > d) return cout << "NO", 0;
  for (int i = head[1]; ~i; i = nx[i]) {
    if (pp == d) break;
    int vv = to[i];
    int u = find(1), v = find(vv);
    if (u != v) {
      fa[u] = v;
      vec.push_back(vv);
      pp++;
    }
  }
  if (pp != d) return cout << "NO", 0;
  cout << "YES\n";
  for (auto x : vec) {
    cout << 1 << " " << x << endl;
  }
  for (int i = 2; i <= n; ++i) {
    for (int j = head[i]; ~j; j = nx[j]) {
      int vv = to[j];
      int u = find(i), v = find(vv);
      if (vv == 1) continue;
      if (u != v) {
        fa[u] = v;
        cout << i << " " << vv << endl;
      }
    }
  }
  return 0;
}
