#ifdef LOCAL
class SS {
   int x[0];
};
extern "C" SS __sanitizer_print_stack_trace();
#define __last_state                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   \
   }                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   \
   ;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   \
   SS x {                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              \
      __sanitizer_print_stack_trace()
#endif
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mp make_pair
#define st first
#define nd second
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0);
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fwd(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(c) (c).begin(), (c).end()
#define sz(X) (int)((X).size())
typedef long double ld;
typedef unsigned long long ull;
typedef long long ll;
#ifdef LOCAL
ostream &operator<<(ostream &out, string str) {
   for (char c : str)
      out << c;
   return out;
}
template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; }
template <class L, class R, class S> ostream &operator<<(ostream &out, tuple<L, R, S> p) {
   auto &[a, b, c] = p;
   return out << "(" << a << ", " << b << ", " << c << ")";
}
template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
   out << '{';
   for (auto it = a.begin(); it != a.end(); it = next(it))
      out << (it != a.begin() ? ", " : "") << *it;
   return out << '}';
}
void dump() { cerr << "\n"; }
template <class T, class... Ts> void dump(T a, Ts... x) {
   cerr << a << ", ";
   dump(x...);
}
#define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...) 42
#endif

typedef vector<bool> vb;

struct SOLVE {
   vector<pii> e;
   int n, limit;
   vb mask;
   int cnt;
   vector<vector<int>> g;
   vector<int> deg;
   vector<int> id;
   typedef pair<int, vb> piv;

   SOLVE(vector<pii> e, int n, int limit) : e(e), n(n), limit(limit), mask(n, false), cnt(0), g(n), deg(n), id(n, -1) {
      for (auto [a, b] : e) {
         g[a].push_back(b);
         g[b].push_back(a);
         deg[a]++;
         deg[b]++;
      }
      for (auto &N : g)
         sort(all(N));
   }

   void add(int x, int p) {
      if (!mask[x]) {
         id[x] = p;
         mask[x] = true;
         for (auto y : g[x])
            deg[y]--;
         cnt++;
      }
   }

   void remove(int x, int p) {
      if (mask[x] && id[x] == p) {
         mask[x] = false;
         for (auto y : g[x])
            deg[y]++;
         cnt--;
      }
   }

   vb combine(vb &a, vb &b) {
      rep(i, sz(a)) a[i] = a[i] || b[i];
      return a;
   }
   piv best(piv &a, piv &b) {
      if (a.st == b.st)
         return {a.st, combine(a.nd, b.nd)};
      return min(a, b);
   }

   piv sum(piv &a, piv &b) { return {a.st + b.st, combine(a.nd, b.nd)}; }

   piv minVC_deg2() {
      auto vis = mask;

      vb result(n);
      vector<int> dist(n);
      int cnt = 0;

      fwd(k, 1, 3) rep(i, n) if (!vis[i] && deg[i] == k) {
         static vector<int> X;
         int j = 0;
         X.push_back(i);
         while (j != sz(X)) {
            auto x = X[j++];
            vis[x] = true;
            for (int y : g[x])
               if (!vis[y]) {
                  vis[y] = true;
                  X.push_back(y);
                  dist[y] = dist[x] + 1;
               }
         }

         if (k == 1) {
            cnt += sz(X) / 2;
            for (int x : X)
               if (dist[x] % 2 || (sz(X) % 2 == 0))
                  result[x] = true;
         }
         if (k == 2) {
            cnt += (sz(X) + 1) / 2;
            for (auto x : X)
               result[x] = true;
         }
         X.clear();
      }

      return {cnt, result};
   }

   piv minVC() {
      if (cnt > limit)
         return {cnt, mask};

      pii high_deg = {0, 0};
      rep(i, n) if (!mask[i]) high_deg = max(high_deg, make_pair(deg[i], i));

      auto [h, v] = high_deg;
      if (h == 0)
         return {cnt, mask};

      if (cnt == limit)
         return {cnt + 1, mask};

      if (h <= 2) {
         piv cur = {cnt, mask};
         piv two = minVC_deg2();
         return sum(cur, two);
      }

      piv res1, res2;

      add(v, v);
      res1 = minVC();
      remove(v, v);

      for (auto t : g[v])
         add(t, v);
      res2 = minVC();
      for (auto t : g[v])
         remove(t, v);

      return best(res1, res2);
   }

   piv solve() {
      auto res = minVC();
      return res;
   }
};

vi trans(vb mask) {
   vi res;
   rep(i, sz(mask)) if (mask[i]) res.push_back(i);
   return res;
}

int32_t main() {
   _upgrade;
   // TEST::solve();

   int Z;
   cin >> Z;
   while (Z--) {
      int n, m, k;
      cin >> n >> m >> k;

      set<pii> TMP;
      rep(i, m) {
         int a, b;
         cin >> a >> b;
         TMP.insert(minmax({--a, --b}));
      }
      vector<pii> U(all(TMP));
      auto [day, mask] = SOLVE(U, n, k).solve();

      if (day > k) {
         cout << -1 << endl;
      } else {
         auto res = trans(mask);
         cout << day << " " << sz(res) << endl;
         for (auto x : res)
            cout << x + 1 << " ";
         cout << endl;
      }
   }
}