#include <bits/stdc++.h>
const int N = 2e5 + 10;
int n, m, d, a, b, components, vis[N], comp[N];
std::vector<int> graph[N];
std::set<int> choosen;
std::queue<int> q;
void dfs(int v) {
  if (comp[v]) return;
  comp[v] = components + 1;
  for (int u : graph[v]) dfs(u);
}
int main() {
  scanf("%d%d%d", &n, &m, &d);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &a, &b);
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  comp[1] = -1;
  for (int i = 2; i <= n; i++) {
    if (!comp[i]) {
      dfs(i);
      components++;
    }
  }
  if (components > d || graph[1].size() < d) {
    printf("NO\n");
  } else {
    printf("YES\n");
    std::sort((graph[1]).begin(), (graph[1]).end(),
              [](int a, int b) -> bool { return comp[a] < comp[b]; });
    for (int i = 0; i < graph[1].size(); i++) {
      if (!i || comp[graph[1][i]] != comp[graph[1][i - 1]]) {
        vis[graph[1][i]] = true;
        choosen.insert(graph[1][i]);
        q.push(graph[1][i]);
        printf("%d %d\n", 1, graph[1][i]);
      }
    }
    for (int u : graph[1]) {
      if (choosen.size() == d)
        break;
      else if (!choosen.count(u)) {
        vis[u] = true;
        choosen.insert(u);
        q.push(u);
        printf("%d %d\n", 1, u);
      }
    }
    vis[1] = true;
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (int u : graph[v]) {
        if (!vis[u]) {
          vis[u] = true;
          q.push(u);
          printf("%d %d\n", v, u);
        }
      }
    }
  }
  return 0;
}
