#include <bits/stdc++.h>
using namespace std;
const long double pi = 4 * atan((long double)1);
const long long mod = 1e9 + 7;
const long long inf = 922337203685477;
const long long nax = 2e5 + 5;
long long n, m, d;
long long vis[nax], used[nax];
vector<vector<long long>> v(nax);
vector<long long> deg;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m >> d;
  for (long long i = 1; i <= m; i++) {
    long long x, y;
    cin >> x >> y;
    if (x > y) {
      swap(x, y);
    }
    if (x == 1) {
      deg.push_back(y);
    } else {
      v[x].push_back(y);
      v[y].push_back(x);
    }
  }
  if ((long long)deg.size() < d) {
    cout << "NO\n";
    return 0;
  }
  for (long long x : deg) {
    if (vis[x] != 0) {
      continue;
    }
    long long flag = x;
    queue<long long> q;
    q.push(x);
    while (!q.empty()) {
      long long cur = q.front();
      q.pop();
      vis[cur] = flag;
      for (auto y : v[cur]) {
        if (!vis[y]) {
          q.push(y);
          vis[y] = flag;
        }
      }
    }
  }
  set<long long> st;
  for (long long x : deg) {
    st.insert(vis[x]);
  }
  if ((long long)st.size() > d) {
    cout << "NO\n";
  } else {
    st.clear();
    long long need = 0;
    for (long long x : deg) {
      if (!st.count(vis[x])) {
        st.insert(x);
        used[x] = 1;
        need++;
        v[1].push_back(x);
        v[x].push_back(1);
      }
    }
    for (long long x : deg) {
      if (need == d) {
        break;
      }
      if (!used[x]) {
        v[1].push_back(x);
        v[x].push_back(1);
        need++;
        used[x] = 1;
      }
    }
    memset(vis, 0, sizeof(vis));
    queue<pair<long long, long long>> q;
    vector<pair<long long, long long>> ans;
    q.push({1, 0});
    while (!q.empty()) {
      auto cur = q.front();
      q.pop();
      vis[cur.first] = 1;
      if (cur.second != 0) {
        ans.push_back({cur.first, cur.second});
      }
      for (auto y : v[cur.first]) {
        if (!vis[y]) {
          vis[y] = 1;
          q.push({y, cur.first});
        }
      }
    }
    cout << "YES" << '\n';
    for (auto x : ans) {
      cout << x.first << " " << x.second << '\n';
    }
  }
}
