#include <bits/stdc++.h>
using namespace std;
const double h = 1e-6;
const int MAX_ = 200005;
inline long long int mul(long long int a, long long int b) {
  return (a * 1ll * b) % 1000000007;
}
inline long long int sub(long long int a, long long int b) {
  long long int c = a - b;
  if (c < 0) c += 1000000007;
  return c;
}
inline long long int add(long long int a, long long int b) {
  long long int c = a + b;
  if (c > 1000000007) c -= 1000000007;
  return c;
}
long long int sqr(long long int x) { return x * x; }
struct graph {
  vector<int> v;
  int par = -1, col = -1;
};
graph G[MAX_];
int cnt;
int n, e;
vector<pair<int, int> > ans;
vector<bool> vis(MAX_, false);
void bfs(int s, int bad) {
  vis[s] = 1;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int from = q.front();
    q.pop();
    G[from].col = cnt;
    if (G[from].par != -1) {
      ans.push_back({from, G[from].par});
    }
    for (int i = 0; i < G[from].v.size(); ++i) {
      int to = G[from].v[i];
      if (to == bad) continue;
      if (!vis[to]) {
        G[to].par = from;
        vis[to] = 1;
        q.push(to);
      }
    }
  }
  ++cnt;
}
bool rule(int a, int b) { return G[a].col < G[b].col; }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int d;
  cin >> n >> e >> d;
  for (long long int i = 0; i < e; i++) {
    int x, y;
    cin >> x >> y;
    G[x].v.push_back(y);
    G[y].v.push_back(x);
  }
  cnt = 0;
  for (int i = 2; i <= n; ++i) {
    if (G[i].col == -1) {
      bfs(i, 1);
    }
  }
  if (cnt > d || d > G[1].v.size()) {
    cout << "NO\n";
    return 0;
  }
  sort(G[1].v.begin(), G[1].v.end(), rule);
  vector<bool> used(G[1].v.size(), false);
  for (int i = 0; i < G[1].v.size(); ++i) {
    int to = G[1].v[i];
    int prev = (i == 0) ? -1 : G[1].v[i - 1];
    if (i == 0 || G[to].col != G[prev].col) {
      ans.push_back({1, to});
      used[i] = 1;
    }
  }
  d -= cnt;
  for (int i = 0; i < G[1].v.size(); ++i) {
    if (d == 0) {
      break;
    }
    int to = G[1].v[i];
    if (used[i] == false) {
      ans.push_back({1, to});
      d--;
    }
  }
  for (int i = 1; i <= n; ++i) {
    G[i].v.clear();
  }
  for (int i = 0; i < ans.size(); ++i) {
    int x = ans[i].first;
    int y = ans[i].second;
    G[x].v.push_back(y);
    G[y].v.push_back(x);
  }
  ans.clear();
  for (int i = 1; i <= n; ++i) {
    vis[i] = false;
  }
  bfs(1, -1);
  cout << "YES\n";
  for (int i = 0; i < ans.size(); ++i) {
    cout << ans[i].first << " " << ans[i].second << "\n";
  }
  return 0;
}
