#include <bits/stdc++.h>
using namespace std;
vector<int> a[200001];
int p[200001];
int n, m;
bool c[200001];
int Find(int x) {
  if (p[x] == x)
    return x;
  else
    return p[x] = Find(p[x]);
}
void Union(int x, int y) {
  x = Find(x);
  y = Find(y);
  p[y] = x;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    a[x].push_back(y);
    a[y].push_back(x);
  }
  for (int i = 1; i <= n; i++) {
    p[i] = i;
  }
  int idx = -1;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (idx == -1 || cnt < a[i].size()) {
      cnt = a[i].size();
      idx = i;
    }
  }
  queue<int> q;
  c[idx] = true;
  for (int i = 0; i < a[idx].size(); i++) {
    Union(idx, a[idx][i]);
    cout << idx << ' ' << a[idx][i] << '\n';
    q.push(a[idx][i]);
    c[a[idx][i]] = true;
  }
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 0; i < a[x].size(); i++) {
      int y = a[x][i];
      if (Find(x) != Find(y)) {
        Union(x, y);
        cout << x << ' ' << y << '\n';
      }
      if (!c[y]) {
        c[y] = true;
        q.push(y);
      }
    }
  }
}
