#include <bits/stdc++.h>
using namespace std;
class DisjointSet {
 public:
  vector<int> parent;
  DisjointSet(int n) : parent(n) {
    for (int i = 0; i < n; i++) parent[i] = i;
  }
  void join(int a, int b) { parent[find(b)] = find(a); }
  int find(int a) { return a == parent[a] ? a : parent[a] = find(parent[a]); }
  bool check(int a, int b) { return find(a) == find(b); }
};
int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int> > g(n + 1);
  int x, y;
  map<int, int> d;
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
    d[x]++;
    d[y]++;
  }
  vector<pair<int, int> > al;
  for (auto nod : d) {
    al.push_back(nod);
  }
  sort(al.begin(), al.end(),
       [](pair<int, int> a, pair<int, int> b) { return a.second > b.second; });
  vector<pair<int, int> > ans;
  DisjointSet dsu(n + 1);
  for (int i = 0; i < (int)al.size(); i++) {
    int node = al[i].first;
    for (auto x : g[node]) {
      if (dsu.check(node, x) == false) {
        ans.push_back({node, x});
        dsu.join(node, x);
      }
    }
  }
  for (auto x : ans) {
    cout << x.first << " " << x.second << "\n";
  }
}
