#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m, d;
  cin >> n >> m >> d;
  vector<vector<int>> g(n, vector<int>());
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  if (g[0].size() < d) {
    cout << "NO" << endl;
    return 0;
  }
  vector<int> visited(n, -1);
  visited[0] = 0;
  int cnt = 0;
  for (int i = 1; i < n; ++i) {
    if (visited[i] != -1) continue;
    ++cnt;
    visited[i] = cnt;
    queue<int> q;
    q.push(i);
    while (!q.empty()) {
      int node = q.front();
      q.pop();
      for (auto nnode : g[node]) {
        if (visited[nnode] != -1) continue;
        visited[nnode] = cnt;
        q.push(nnode);
      }
    }
  }
  if (cnt > d) {
    cout << "NO" << endl;
    return 0;
  }
  cout << "YES" << endl;
  vector<bool> used(n, false);
  vector<bool> marked(n, false);
  queue<int> q;
  for (auto node : g[0]) {
    if (used[visited[node]]) continue;
    used[visited[node]] = true;
    marked[node] = true;
    q.push(node);
    cout << 1 << " " << node + 1 << endl;
    --d;
  }
  for (auto node : g[0]) {
    if (marked[node]) continue;
    if (d == 0) break;
    marked[node] = true;
    q.push(node);
    --d;
    cout << 1 << " " << node + 1 << endl;
  }
  marked[0] = true;
  while (!q.empty()) {
    int node = q.front();
    q.pop();
    for (auto nnode : g[node]) {
      if (marked[nnode]) continue;
      marked[nnode] = true;
      cout << node + 1 << " " << nnode + 1 << endl;
      q.push(nnode);
    }
  }
  return 0;
}
