#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > adjlist;
vector<int> visited;
vector<pair<int, int> > vp;
void dfs(int s) {
  visited[s] = 1;
  for (int i = 0; i < adjlist[s].size(); i++) {
    int v = adjlist[s][i];
    if (visited[v] == 0) {
      vp.push_back({s, v});
      dfs(v);
    }
  }
}
int coun = 0;
void ufo(int s) {
  visited[s] = 1;
  coun++;
  for (int i = 0; i < adjlist[s].size(); i++) {
    int v = adjlist[s][i];
    if (visited[v] == 0) {
      ufo(v);
    }
  }
}
int main() {
  int n, m, d;
  cin >> n >> m >> d;
  adjlist.assign(n + 1, vector<int>());
  visited.assign(n + 1, 0);
  int a, b;
  for (int i = 0; i < m; i++) {
    cin >> a >> b;
    adjlist[a].push_back(b);
    adjlist[b].push_back(a);
  }
  if (adjlist[1].size() >= d) {
    visited[1] = 1;
    vector<pair<int, int> > vi;
    for (int i = 0; i < adjlist[1].size(); i++) {
      int v = adjlist[1][i];
      coun = 0;
      if (visited[v] == 0) ufo(v);
      vi.push_back({coun, v});
    }
    cout << '\n';
    visited.clear();
    visited.assign(n + 1, 0);
    sort(vi.begin(), vi.end(), greater<pair<int, int> >());
    for (int i = 0; i < d; i++) visited[vi[i].second] = 1;
    visited[1] = 1;
    for (int i = 0; i < d; i++) {
      int v = vi[i].second;
      dfs(v);
      vp.push_back({1, v});
    }
    bool is = true;
    for (int i = 1; i <= n; i++) {
      if (visited[i] == 0) is = false;
    }
    if (is) {
      cout << "YES\n";
      for (int i = 0; i < vp.size(); i++)
        cout << vp[i].first << " " << vp[i].second << '\n';
    } else
      cout << "NO";
  } else
    cout << "NO";
  return 0;
}
