#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> edges;
vector<int> con;
vector<bool> vb;
void dfs(int i, int j) {
  if (vb[i]) return;
  vb[i] = true;
  for (auto k : edges[i]) dfs(k, j);
}
int main() {
  int s, r, d;
  scanf("%d %d %d", &s, &r, &d);
  edges.resize(s + 1);
  vb.resize(s + 1);
  for (int i = 0; i != r; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  vb[1] = true;
  for (auto i : edges[1]) {
    if (!vb[i]) {
      con.emplace_back(i);
      dfs(i, con.size() - 1);
    }
  }
  if (edges[1].size() < d || con.size() > d) {
    puts("NO");
    return 0;
  }
  puts("YES");
  queue<int> q;
  for (int i = 1; i <= s; i++) vb[i] = false;
  for (int i = 0; i != con.size(); i++) {
    printf("1 %d\n", con[i]);
    vb[con[i]] = true;
    q.push(con[i]);
    d--;
  }
  for (int i = 0; d && i != edges[1].size(); i++) {
    if (!vb[edges[1][i]]) {
      printf("1 %d\n", edges[1][i]);
      vb[edges[1][i]] = true;
      d--;
      q.push(edges[1][i]);
    }
  }
  vb[1] = true;
  while (!q.empty()) {
    vb[q.front()] = true;
    int i = q.front();
    q.pop();
    for (int j : edges[i]) {
      if (!vb[j]) {
        printf("%d %d\n", i, j);
        q.push(j), vb[j] = true;
      }
    }
  }
}
