#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int n;
int m;
int d;
int cnt;
int ans;
int p[N];
set<int> b;
int used[N];
vector<int> t;
vector<int> g[N];
vector<pair<int, int>> a;
vector<pair<int, int>> c;
vector<pair<int, int>> res;
vector<vector<int>> comp;
void dfs(int v) {
  used[v] = 1;
  t.push_back(v);
  for (auto to : g[v]) {
    if (used[to] == 1) continue;
    dfs(to);
  }
}
int get(int x) { return (p[x] == x ? x : p[x] = get(p[x])); }
int merge(int a, int b) {
  int x = a, y = b;
  a = get(a);
  b = get(b);
  if (a == b) return false;
  p[b] = a;
  res.push_back({x, y});
  return true;
}
int main() {
  cin >> n >> m >> d;
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    if (x > y) swap(x, y);
    a.push_back({x, y});
    if (x == 1) {
      ans++;
      b.insert(y);
    } else {
      g[x].push_back(y);
      g[y].push_back(x);
    }
  }
  for (int i = 1; i <= n; i++) p[i] = i;
  for (int i = 2; i <= n; i++) {
    if (used[i] == 0) {
      cnt++;
      dfs(i);
      int y = 0;
      for (auto x : t)
        if (b.count(x)) y = x;
      if (y == 0) {
        cout << "NO\n";
        return 0;
      }
      b.erase(y);
      merge(1, y);
      t.clear();
    }
  }
  if (cnt > d || ans < d) {
    cout << "NO\n";
    return 0;
  }
  d -= cnt;
  for (auto x : a) {
    if (x.first == 1) {
      if (d > 0 && merge(1, x.second)) d--;
    }
  }
  if (d > 0) {
    cout << "NO\n";
    return 0;
  }
  for (auto x : a) {
    if (x.first == 1) continue;
    merge(x.first, x.second);
  }
  if ((int)res.size() != n - 1) {
    cout << "NO\n";
    return 0;
  }
  cout << "YES\n";
  for (auto x : res) cout << x.first << " " << x.second << "\n";
}
