#include <bits/stdc++.h>
using namespace std;
const int maxx = 1e6 + 2;
vector<int> a[maxx];
int aa[maxx], bb[maxx];
int par[maxx];
vector<int> b;
bool vis[maxx];
bool book[maxx];
void dfs(int x) {
  vis[x] = 1;
  for (int i = 0; i < a[x].size(); i++) {
    int t = a[x][i];
    if (vis[t]) continue;
    dfs(t);
  }
}
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
int main() {
  int n, m, d;
  cin >> n >> m >> d;
  for (int i = 1; i <= n; i++) par[i] = i;
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    aa[i] = x, bb[i] = y;
    a[x].push_back(y);
    a[y].push_back(x);
  }
  int maxn = a[1].size(), ans = 0;
  vis[1] = 1;
  for (int i = 0; i < a[1].size(); i++) {
    int t = a[1][i];
    if (vis[t]) continue;
    dfs(t);
    b.push_back(t);
    ans++;
  }
  if (maxn < d || ans > d) return 0 * puts("NO");
  puts("YES");
  for (int i = 0; i < b.size(); i++) {
    cout << 1 << " " << b[i] << endl;
    int x;
    x = find(b[i]);
    book[x] = 1;
    par[x] = 1;
  }
  for (int i = 0; i < a[1].size(); i++) {
    if (ans < d && !book[a[1][i]]) {
      cout << 1 << " " << a[1][i] << endl;
      par[a[1][i]] = 1;
      book[a[1][i]] = 1;
      ans++;
    }
  }
  for (int i = 1; i <= m; i++) {
    int x, y;
    x = find(aa[i]), y = find(bb[i]);
    if (x == y) continue;
    if (aa[i] > bb[i]) swap(aa[i], bb[i]);
    if (aa[i] == 1) continue;
    cout << aa[i] << " " << bb[i] << endl;
    par[x] = y;
  }
  return 0;
}
