#include <bits/stdc++.h>
const long long mod = 1000000000 + 7;
const long long INF = 9000000000000000000;
using namespace std;
void yes() { cout << "YES" << endl; }
void no() { cout << "NO" << endl; }
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long lcm(long long a, long long b) { return (a * b / (gcd(a, b))); }
long long root(vector<long long>& arr, long long a) {
  if (arr[a] < 0) return a;
  return arr[a] = root(arr, arr[a]);
}
void Union(vector<long long>& arr, long long a, long long b) {
  long long x1 = root(arr, a);
  long long y1 = root(arr, b);
  if (x1 == y1) return;
  if (arr[x1] < arr[y1]) {
    arr[x1] += arr[y1];
    arr[y1] = x1;
  } else {
    arr[y1] += arr[x1];
    arr[x1] = y1;
  }
}
const long long N = 200000 + 5;
vector<pair<long long, long long> > edge;
long long nodes, edges;
vector<long long> parent(N);
vector<pair<long long, long long> > ans;
long long degree[N];
void kruskals() {
  for (long long i = 0; i < edges; i++) {
    long long u = edge[i].first, v = edge[i].second;
    long long par_u = root(parent, u), par_v = root(parent, v);
    if (par_u != par_v) {
      Union(parent, u, v);
      ans.push_back({u, v});
    }
  }
}
void solve() {
  long long n, e, m, d;
  string s;
  cin >> nodes >> edges;
  n = nodes;
  e = edges;
  memset(degree, 0, sizeof(degree));
  for (long long i = 0; i <= n; i++) parent[i] = -1;
  for (long long i = 0; i < e; i++) {
    long long u, v;
    cin >> u >> v;
    degree[u]++, degree[v]++;
    edge.push_back({u, v});
  }
  long long maxnode = 1, maxd = -1;
  for (long long i = 1; i <= n; i++)
    if (degree[i] > maxd) maxd = degree[i], maxnode = i;
  for (long long i = 0; i < edges; i++) {
    long long u = edge[i].first, v = edge[i].second;
    if (u != maxnode && v != maxnode) continue;
    long long par_u = root(parent, u), par_v = root(parent, v);
    if (par_u != par_v) {
      Union(parent, u, v);
      ans.push_back({u, v});
    }
  }
  for (long long i = 0; i < edges; i++) {
    long long u = edge[i].first, v = edge[i].second;
    long long par_u = root(parent, u), par_v = root(parent, v);
    if (par_u != par_v) {
      Union(parent, u, v);
      ans.push_back({u, v});
    }
  }
  for (auto x : ans) cout << x.first << " " << x.second << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  long long tests = 1;
  while (tests--) {
    solve();
  }
  return 0;
}
