#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int d[N];
vector<int> G[N];
int vis[N];
queue<int> Q;
void dfs(int u, int fa) {
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if (vis[v] == 0) {
      vis[v] = 1;
      dfs(v, u);
    }
  }
}
int main() {
  int n, i, j, k, o, p, l, m, X;
  scanf("%d %d %d", &n, &m, &X);
  for (i = 1; i <= m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    G[x].push_back(y);
    G[y].push_back(x);
    d[x]++, d[y]++;
  }
  if (d[1] < X) {
    printf("NO");
    return 0;
  }
  int num = 0;
  vis[1] = 2;
  for (i = 0; i < G[1].size(); i++) {
    int v = G[1][i];
    if (vis[v] == 0) {
      vis[v] = 2;
      dfs(v, 1);
      num++;
    }
  }
  if (num > X) {
    printf("NO");
    return 0;
  }
  printf("YES\n");
  vis[1] = 2;
  for (i = 0; i < G[1].size(); i++) {
    int v = G[1][i];
    if (vis[v] == 2) {
      printf("1 %d\n", v);
      Q.push(v);
    }
  }
  if (num < X) {
    for (i = 0; i < G[1].size(); i++) {
      int v = G[1][i];
      if (vis[v] == 1) {
        printf("1 %d\n", v);
        vis[v] = 2;
        Q.push(v);
        num++;
        if (num == X) break;
      }
    }
  }
  while (!Q.empty()) {
    int tot = Q.front();
    Q.pop();
    for (i = 0; i < G[tot].size(); i++) {
      int v = G[tot][i];
      if (vis[v] == 1) {
        printf("%d %d\n", tot, v);
        Q.push(v);
        vis[v] = 2;
      }
    }
  }
  return 0;
}
