#include <bits/stdc++.h>
#define dbg(x) " [" << #x << ": " << (x) << "] "
using namespace std;
template<typename A, typename B>
ostream& operator<<(ostream& out, const pair<A,B>& p) {
    return out << "(" << p.first << ", " << p.second << ")";
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& c) {
    out << "{";
    for(auto it = c.begin(); it != c.end(); it++) {
        if(it != c.begin()) out << ", ";
        out << *it;
    }
    return out << "}";
}
struct Test {
    int n,m,k;
    vector<int> u;
    int mn;
    vector<int> in_ans;
    void rec(vector<vector<int>> g, int used, int edges) {
        if(edges == 0) {
            if(used == 0) return;
            if(used < mn) {
                mn = used;
                in_ans.assign(n, 0);
            }
            if(used == mn) {
                for(int i = 0; i < n; i++) {
                    if(u[i] == 2) {
                        in_ans[i] = 1;
                    }
                }
            }
            return;
        }
        if(used >= k || used >= mn) return;
        int j = -1;
        for(int i = 0; i < n; i++) {
            if(u[i]) continue;
            if(j == -1 || g[i].size() > g[j].size()) j = i;
        }
        if(edges > g[j].size() * (k - used)) return;
        vector<int> nxt = g[j];
        for(int v : nxt) {
            g[v].erase(find(g[v].begin(), g[v].end(), j));
        }
        g[j].clear();
        u[j] = 2;
        edges -= nxt.size();
        rec(g, used + 1, edges);
        u[j] = 1;
        for(int v : nxt) {
            vector<int> nxt2 = g[v];
            for(int vv : nxt2) {
                g[vv].erase(find(g[vv].begin(), g[vv].end(), v));
            }
            g[v].clear();
            edges -= nxt2.size();
            u[v] = 2;
        }
        rec(g, used + nxt.size(), edges);
        for(int v : nxt) u[v] = 0;
        u[j] = 0;
    }
    void solve() {
        cin >> n >> m >> k;
        set<pair<int,int>> st;
        vector<vector<int>> g(n);
        u.resize(n);
        vector<pair<int,int>> e;
        vector<int> d(n);
        in_ans.resize(n);
        for(int i = 0; i < m; i++) {
            int a,b;
            cin >> a >> b;
            a--;
            b--;
            if(a > b) swap(a, b);
            if(st.contains({a,b})) continue;
            st.insert({a,b});
            e.push_back({a,b});
            d[a]++;
            d[b]++;
        }
        int used = 0;
        for(int i = 0; i < n; i++) {
            if(d[i] > k) {
                u[i] = 2;
                in_ans[i] = 1;
                used++;
            }
        }
        int edges = 0;
        for(auto [a,b] : e) {
            if(!in_ans[a] && !in_ans[b]) {
                g[a].push_back(b);
                g[b].push_back(a);
                edges++;
            }
        }
        for(int i = 0; i < n; i++) {
            if(g[i].size() == 0 && !in_ans[i]) u[i] = 1;
        }
        in_ans.assign(n, 0);
        mn = k + 1;
        rec(g, used, edges);
        if(mn == k + 1) {
            cout << -1 << '\n';
            return;
        }
        cout << mn << " ";
        int y = 0;
        for(int i = 0; i < n; i++) y += in_ans[i];
        cout << y << '\n';
        y = 0;
        for(int i = 0; i < n; i++) {
            if(in_ans[i]) {
                if(y) cout << " ";
                cout << i + 1;
                y++;
            }
        }
        cout << '\n';
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int test_num = 1;
    cin >> test_num;
    for(int i = 1; i <= test_num; i++) {
        Test t;
        t.solve();
    }
    return 0;
}

answer.code: In member function ‘void Test::solve()’:
answer.code:81:19: error: ‘class std::set<std::pair<int, int> >’ has no member named ‘contains’
   81 |             if(st.contains({a,b})) continue;
      |                   ^~~~~~~~
answer.code:96:18: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’
   96 |         for(auto [a,b] : e) {
      |                  ^