#include <bits/stdc++.h>
using namespace std;
inline char gc() { return getchar(); }
template <class T>
int read(T &ans) {
  ans = 0;
  char ch = gc();
  T f = 1;
  while (!isdigit(ch)) {
    if (ch == EOF) return -1;
    if (ch == '-') f = -1;
    ch = gc();
  }
  while (isdigit(ch)) ans = ans * 10 + ch - '0', ch = gc();
  ans *= f;
  return 1;
}
template <class T1, class T2>
int read(T1 &a, T2 &b) {
  return read(a) != EOF && read(b) != EOF ? 2 : EOF;
}
template <class T1, class T2, class T3>
int read(T1 &a, T2 &b, T3 &c) {
  return read(a, b) != EOF && read(c) != EOF ? 3 : EOF;
}
const int Maxn = 1100000;
const int inf = 0x3f3f3f3f;
int n, m, D, to[Maxn], nxt[Maxn], first[Maxn], tot = 1;
int vis[Maxn], d[Maxn], u, v, cnt;
queue<int> q;
vector<int> vi[Maxn];
inline void add(int u, int v) {
  to[tot] = v;
  nxt[tot] = first[u];
  first[u] = tot++;
  to[tot] = u;
  nxt[tot] = first[v];
  first[v] = tot++;
}
void dfs(int root) {
  vis[root] = cnt;
  for (int i = first[root]; i; i = nxt[i])
    if (!vis[to[i]]) dfs(to[i]);
}
signed main() {
  read(n, m, D);
  for (int i = 1; i <= m; i++) {
    read(u, v);
    add(u, v);
    d[u]++;
    d[v]++;
  }
  if (d[1] >= D && D) {
    vis[1] = ++cnt;
    for (int i = first[1]; i; i = nxt[i])
      if (vis[to[i]])
        vi[vis[to[i]]].push_back(to[i]);
      else
        cnt++, dfs(to[i]), vi[cnt].push_back(to[i]);
    if (cnt - 1 > D)
      puts("NO");
    else {
      memset(vis, 0, sizeof(vis));
      vis[1] = 1;
      puts("YES");
      for (int i = 2; i <= cnt; i++)
        printf("1 %d\n", vi[i][0]), vis[vi[i][0]] = 1, q.push(vi[i][0]);
      D -= cnt - 1;
      for (int i = 2; i <= cnt; i++) {
        for (int j = 1; j < vi[i].size(); j++) {
          if (!D) break;
          D--;
          printf("1 %d\n", vi[i][j]);
          vis[vi[i][j]] = 1;
          q.push(vi[i][j]);
        }
      }
      while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = first[now]; i; i = nxt[i])
          if (!vis[to[i]]) {
            vis[to[i]] = 1;
            printf("%d %d\n", now, to[i]);
            q.push(to[i]);
          }
      }
    }
  } else
    puts("NO");
  return 0;
}
