#include <bits/stdc++.h>
using namespace std;
int vis[200010];
vector<int> v[200010];
void dfs(int x, int cc) {
  vis[x] = cc;
  for (int i = 0; i < v[x].size(); ++i) {
    if (vis[v[x][i]] == 0) {
      dfs(v[x][i], cc);
    }
  }
}
int main() {
  int n, m, d;
  cin >> n >> m >> d;
  int cont1 = 0;
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    if (x == 1) {
      cont1++;
      v[x].push_back(y);
    } else if (y == 1) {
      cont1++;
      v[y].push_back(x);
    } else {
      v[x].push_back(y);
      v[y].push_back(x);
    }
  }
  int contc = 0;
  for (int i = 2; i <= n; ++i) {
    if (vis[i] == 0) {
      dfs(i, ++contc);
    }
  }
  if (cont1 < d || d < contc) {
    printf("NO\n");
    return 0;
  }
  vector<int> gambiarra[contc + 1];
  for (int i = 0; i < v[1].size(); ++i) {
    v[v[1][i]].push_back(1);
    gambiarra[vis[v[1][i]]].push_back(v[1][i]);
  }
  int it = 1;
  while (true) {
    if (d == 0) break;
    if (!gambiarra[it].empty()) {
      gambiarra[it].pop_back();
      d--;
    }
    if (++it > contc) {
      it = 1;
    }
  }
  set<int> s;
  for (int i = 1; i < contc + 1; ++i) {
    for (int j = 0; j < gambiarra[i].size(); ++j) {
      s.insert(gambiarra[i][j]);
    }
    printf("\n");
  }
  for (int i = 1; i <= n; ++i) {
    vis[i] = 0;
  }
  queue<int> q;
  q.push(1);
  printf("YES\n");
  vis[1] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < v[u].size(); ++i) {
      if (u == 1 && s.count(v[u][i])) continue;
      if (vis[v[u][i]] == 0) {
        vis[v[u][i]] = 1;
        q.push(v[u][i]);
        printf("%d %d\n", u, v[u][i]);
      }
    }
  }
}
