#include <bits/stdc++.h>
const long double pi = acos((long double)-1);
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
const int N = 2.1e5;
const long double eps = 1e-8;
using namespace std;
int sign(long double a) { return a < -eps ? -1 : a > eps; }
int db_cmp(long double a, long double b) { return sign(a - b); }
std::vector<int> node[N];
bool vis[N];
int uni[N];
void dfs(int r, int now) {
  uni[now] = r;
  for (int v : node[now]) {
    if (v != 1 && vis[v] == 0) {
      vis[v] = 1;
      dfs(r, v);
    }
  }
}
int main() {
  int n, m, u, v, d;
  scanf("%d%d%d", &n, &m, &d);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &u, &v);
    node[u].push_back(v);
    node[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) uni[i] = i;
  vis[1] = 1;
  for (int v : node[1]) {
    if (vis[v] == 0) {
      vis[v] = 1;
      dfs(v, v);
    }
  }
  memset(vis, 0, sizeof(vis));
  vis[1] = 1;
  int cnt = 0;
  for (int v : node[1]) {
    if (uni[v] == v) cnt++;
  }
  if (d >= cnt && d <= node[1].size()) {
    puts("YES");
    queue<int> que;
    for (int v : node[1]) {
      if (uni[v] == v) {
        vis[v] = 1;
        que.push(v);
        printf("%d %d\n", 1, v);
      } else if (cnt < d) {
        vis[v] = 1;
        que.push(v);
        printf("%d %d\n", 1, v);
        cnt++;
      }
    }
    while (que.size()) {
      u = que.front();
      que.pop();
      for (int v : node[u])
        if (vis[v] == 0) {
          vis[v] = 1;
          printf("%d %d\n", u, v);
          que.push(v);
        }
    }
  } else
    puts("NO");
  return 0;
}
