#include <bits/stdc++.h>
using namespace std;
inline long long int modadd(long long int n, long long int m,
                            long long int p = 1000000007) {
  return ((n + m) % p + p) % p;
}
inline long long int modsub(long long int n, long long int m,
                            long long int p = 1000000007) {
  return ((n - m + p) % p + p) % p;
}
inline long long int modpro(long long int n, long long int m,
                            long long int p = 1000000007) {
  return (((n % p) * (m % p)) % p + p) % p;
}
unsigned long long int powe(long long int first, long long int second) {
  unsigned long long int res = 1;
  while (second > 0) {
    if (second & 1) res = res * first;
    second = second >> 1;
    first = first * first;
  }
  return res;
}
long long int modpow(long long int first, long long int second,
                     long long int p = 1000000007) {
  long long int res = 1;
  while (second > 0) {
    if (second & 1) res = modpro(res, first, p);
    second = second >> 1;
    first = modpro(first, first, p);
  }
  return res;
}
inline long long int modInverse(long long int n, long long int p = 1000000007) {
  if (n == 1) return 1;
  return modpow(n, p - 2, p);
}
inline long long int moddiv(long long int n, long long int m,
                            long long int p = 1000000007) {
  return modpro(n, modInverse(m, p), p);
}
inline long long int modadd3(long long int first, long long int second,
                             long long int z, long long int p = 1000000007) {
  return modadd(modadd(first, second, p), z, p);
}
inline long long int modadd4(long long int first, long long int second,
                             long long int z, long long int w,
                             long long int p = 1000000007) {
  return modadd(modadd(first, second, p), modadd(z, w, p), p);
}
inline long long int modnCr(long long int fac[], int n, int r,
                            long long int p = 1000000007) {
  if (r == 0) return 1;
  return modpro(fac[n], modInverse(modpro(fac[r], fac[n - r], p), p), p);
}
template <typename T>
inline T max3(T first, T second, T z) {
  return max(max(first, second), z);
}
template <typename T>
inline T max4(T first, T second, T z, T w) {
  return max(max3(first, second, w), z);
}
template <typename T>
inline T min3(T first, T second, T z) {
  return min(min(first, second), z);
}
template <typename T>
inline T min4(T first, T second, T z, T w) {
  return min(min3(first, second, w), z);
}
template <typename T>
void printArr(T *arr, int s, int n) {
  for (int i = s; i <= n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
vector<int> parent, rank_;
void makeSet(int first) {
  parent[first] = first;
  rank_[first] = 0;
}
int findSet(int first) {
  if (first != parent[first]) parent[first] = findSet(parent[first]);
  return parent[first];
}
void unionSets(int first, int second) {
  int px = findSet(first);
  int py = findSet(second);
  if (px == py) return;
  if (rank_[px] < rank_[py]) {
    parent[px] = py;
  } else if (rank_[py] < rank_[px]) {
    parent[py] = px;
  } else {
    parent[py] = px;
    rank_[px]++;
  }
}
vector<int> adj[200007];
vector<int> adj2[200007];
vector<pair<int, int> > ans;
bool vis[200007];
void dfs(int first) {
  vis[first] = 1;
  for (int u : adj[first]) {
    if (vis[u]) continue;
    ans.push_back({first, u});
    dfs(u);
  }
}
vector<int> v;
void dfs2(int first) {
  vis[first] = 1;
  v.push_back(first);
  for (int u : adj[first]) {
    if (vis[u]) continue;
    dfs2(u);
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  int erer = 1;
  for (int erer2 = (1); erer2 < (erer + 1); erer2++) {
    int n, m, d;
    cin >> n >> m >> d;
    parent.resize(n + 2);
    rank_.resize(n + 2);
    for (int i = (0); i < (m); i++) {
      int u, v;
      cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
    if (((long long int)(adj[1]).size()) < d) {
      cout << "NO";
      return 0;
    }
    vis[1] = 1;
    for (int i = (1); i < (n + 1); i++) makeSet(i);
    for (int first : adj[1]) {
      v.clear();
      if (!vis[first]) dfs2(first);
      for (int u : v) {
        unionSets(first, u);
      }
    }
    int vv[200007] = {};
    vector<int> tod, res;
    for (int first : adj[1]) {
      if (!vv[findSet(first)]) {
        tod.push_back(first);
        vv[findSet(first)] = 1;
      } else
        res.push_back(first);
    }
    if (((long long int)(tod).size()) > d) {
      cout << "NO";
      return 0;
    } else if (((long long int)(tod).size()) < d) {
      for (int first : res) {
        if (((long long int)(tod).size()) == d) break;
        tod.push_back(first);
      }
    }
    memset(vis, 0, sizeof(vis));
    vis[1] = 1;
    for (int first : tod) {
      vis[first] = 1;
      ans.push_back({1, first});
    }
    for (int first : tod) {
      dfs(first);
    }
    if (((long long int)(ans).size()) != n - 1) {
      cout << "NO";
      return 0;
    }
    cout << "YES" << endl;
    for (auto u : ans) cout << (u.first) << " " << (u.second) << endl;
  }
  return 0;
}
