#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vii = vector<ii>;
using vb = vector<bool>;
using ll = long long;
template <typename A, typename B>
istream &operator>>(istream &in, pair<A, B> &p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T>
istream &operator>>(ifstream &in, vector<T> &v) {
  for (int i = 0; i < (int)v.size(); ++i) {
    in >> v[i];
  }
  return in;
}
int main() {
  int n, m;
  cin >> n >> m;
  vvi graph(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  int best = 0;
  for (int u = 0; u < n; ++u)
    if (graph[u].size() > graph[best].size()) best = u;
  vb visited(n);
  visited[best] = true;
  queue<int> q;
  q.push(best);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : graph[u]) {
      if (visited[v]) continue;
      visited[v] = true;
      cout << u + 1 << " " << v + 1 << endl;
      q.push(v);
    }
  }
}
