#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000;
int n, m, d;
pair<int, int> edge[maxn];
bool used[maxn];
int rnk[maxn], par[maxn], col[maxn];
vector<int> graph[maxn];
int s = 0;
int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
void unionf(int x, int y) {
  if (rnk[x] < rnk[y]) swap(x, y);
  if (rnk[x] == rnk[y]) rnk[x]++;
  par[y] = x;
}
void dfs1(int c) {
  col[c] = s;
  for (int i : graph[c]) {
    if (!i || col[i]) continue;
    dfs1(i);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m >> d;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    edge[i] = {a, b};
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  if (graph[0].size() < d) {
    cout << "NO" << '\n';
    return 0;
  }
  for (int i = 1; i < n; i++) {
    par[i] = i;
    if (!col[i]) {
      s++;
      dfs1(i);
    }
  }
  if (s > d) {
    cout << "NO" << '\n';
    return 0;
  }
  vector<pair<int, int> > ans;
  for (int i : graph[0]) {
    if (!used[col[i]]) {
      used[col[i]] = 1;
      ans.push_back({1, i + 1});
      unionf(0, i);
      d--;
    }
  }
  for (int i : graph[0]) {
    if (!d) break;
    int x = find(0), y = find(i);
    if (x != y) {
      ans.push_back({1, i + 1});
      unionf(x, y);
      d--;
    }
  }
  for (int i = 0; i < m; i++) {
    int a = edge[i].first, b = edge[i].second;
    if (!a || !b) continue;
    int x = find(a), y = find(b);
    if (x != y) {
      ans.push_back({a + 1, b + 1});
      unionf(x, y);
    }
  }
  cout << "YES" << '\n';
  for (pair<int, int> i : ans) cout << i.first << " " << i.second << '\n';
  return 0;
}
