#include <bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;
int inf = 1e15;
int n, m, k, q;
vector<int> v[200003], vv[200003];
vector<pair<int, int>> ans;
bool vis[200003];
bool M[200003];
void dfs(int x, int y) {
  if (y != -1) vv[y].push_back(x);
  vis[x] = 1;
  for (auto pp : v[x]) {
    if (vis[pp]) continue;
    if (y == -1) cout << x << ' ' << pp << endl;
    dfs(pp, y);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  while (m--) {
    int a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    v[a].push_back(b);
    if (a != 1) v[b].push_back(a);
  }
  int d1 = v[1].size();
  for (auto pp : v[1]) {
    M[pp] = 1;
  }
  int a = 0;
  for (int i = 2; i <= n; i++) {
    if (vis[i]) continue;
    dfs(i, i);
    a++;
  }
  if (a > k || k > d1) return cout << "NO", 0;
  cout << "YES" << endl;
  memset(vis, 0, sizeof vis);
  vis[1] = 1;
  for (int i = 2; i <= n; i++) {
    for (auto pp : vv[i]) {
      if (M[pp]) {
        M[pp] = 0;
        vis[pp] = 1;
        cout << "1 " << pp << endl;
        vv[1].push_back(pp);
        k--;
        break;
      }
    }
  }
  for (int i = 2; i <= n; i++) {
    for (auto pp : vv[i]) {
      if (!k) break;
      if (M[pp]) {
        M[pp] = 0;
        vis[pp] = 1;
        cout << "1 " << pp << endl;
        vv[1].push_back(pp);
        k--;
        if (!k) break;
      }
    }
    if (!k) break;
  }
  for (auto pp : vv[1]) dfs(pp, -1);
  return 0;
}
