#include <bits/stdc++.h>
using namespace std;
vector<int> v[200005], sol;
set<int> s;
int book[200005], can[200005];
void dfs(int k, vector<int>& t) {
  for (int i = 0; i < v[k].size(); i++) {
    if (book[v[k][i]] == 0) {
      book[v[k][i]] = 1;
      t.push_back(v[k][i]);
      dfs(v[k][i], t);
    }
  }
}
void dfs(int k) {
  for (int i = 0; i < v[k].size(); i++) {
    if (book[v[k][i]] == 0) {
      book[v[k][i]] = 1;
      printf("%d %d\n", k, v[k][i]);
      dfs(v[k][i]);
    }
  }
}
int main() {
  int n, m, k, q, w;
  scanf("%d%d%d", &n, &m, &k);
  while (m--) {
    scanf("%d%d", &q, &w);
    v[q].push_back(w);
    v[w].push_back(q);
  }
  if (v[1].size() < k) {
    puts("NO");
    return 0;
  }
  for (int i = 0; i < v[1].size(); i++) s.insert(v[1][i]);
  book[1] = 1;
  int yes = 0;
  for (int i = 2; i <= n; i++) {
    if (book[i] == 0) {
      book[i] = 1;
      vector<int> t = {i};
      dfs(i, t);
      int qq = 0, ww = 0;
      for (int j = 0; j < t.size(); j++) {
        if (s.count(t[j])) {
          if (qq == 0) can[t[j]] = 1;
          qq++;
        }
      }
      yes++;
    }
  }
  if (yes > k) {
    puts("NO");
    return 0;
  }
  int t = k - yes;
  for (auto it = s.begin(); it != s.end(); it++) {
    if (can[*it] == 1)
      sol.push_back(*it);
    else if (t > 0) {
      t--;
      sol.push_back(*it);
    }
  }
  memset(book, 0, sizeof book);
  book[1] = 1;
  puts("YES");
  for (int i = 0; i < sol.size(); i++) {
    printf("%d %d\n", 1, sol[i]);
    book[sol[i]] = 1;
  }
  for (int i = 0; i < sol.size(); i++) dfs(sol[i]);
}
