#include <bits/stdc++.h>
using namespace std;

// 定义全局变量
int t, n, m, k;  // t:测试用例数, n:顶点数, m:边数, k:目标覆盖数
int d[1005], tmp[1005], now[1005];  // d:度数, tmp:临时存储度数, now:当前选择的顶点
int st[1005], top;  // st:栈, top:栈顶指针
bool ans[1005], tot[1005], vis[1005];  // ans:最终答案, tot:临时覆盖集合, vis:访问标记
pair<int, int> e[3005];  // 存储边的数组
vector<int> g[1005];  // 邻接表表示的图

// 添加边到图中
inline void add(int x, int y) {
    g[x].emplace_back(y), g[y].emplace_back(x);
    d[x]++, d[y]++;  // 更新顶点度数
}

// 深度优先搜索遍历连通分量
inline void dfs2(int v) {
    st[++top] = v, vis[v] = 1;  // 将顶点压入栈并标记为已访问

    for (int i : g[v])
        if (!vis[i])
            dfs2(i);  // 递归访问未访问的邻居
}

// 主DFS函数，用于寻找最小顶点覆盖
inline void dfs(int step, int cnt = 0) {
    // step: 当前处理的顶点编号
    // cnt: 当前已选择的顶点数量
    
    if (cnt > k) return;  // 剪枝：如果已选择顶点数超过k，直接返回

    if (step > n) {
        // 基本情况：已处理完所有顶点
        for (int i = 1; i <= n; i++)
            vis[i] = tot[i] = now[i];  // 初始化访问标记和临时覆盖集合

        // 处理度数为1的顶点构成的连通分量
        for (int i = 1; i <= n; i++) {
            if (d[i] == 1 && !vis[i]) {
                top = 0, dfs2(i);  // 遍历连通分量

                if ((cnt += top >> 1) > k) return;  // 更新计数并检查是否超过k

                // 根据连通分量大小的奇偶性选择覆盖策略
                if (top & 1)
                    for (int j = 2; j < top; j += 2)
                        tot[st[j]] = 1;  // 奇数情况：选择第2,4,6...个顶点
                else
                    for (int j = 1; j <= top; j++)
                        tot[st[j]] = 1;  // 偶数情况：选择所有顶点
            }
        }

        // 处理度数为2的顶点构成的连通分量
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && d[i] == 2) {
                top = 0, dfs2(i);  // 遍历连通分量

                if ((cnt += (top + 1) >> 1) > k) return;  // 更新计数并检查

                for (int j = 1; j <= top; j++)
                    tot[st[j]] = 1;  // 选择所有顶点
            }
        }

        // 更新最优解
        if (cnt < k) {
            k = cnt;  // 更新最小覆盖数
            for (int i = 1; i <= n; i++)
                ans[i] = tot[i];  // 更新答案
        } else {
            for (int i = 1; i <= n; i++)
                ans[i] |= tot[i];  // 合并到当前答案
        }

        return;
    }

    // 剪枝：如果当前顶点度数≤2，跳过选择该顶点的情况
    if (d[step] <= 2)
        return dfs(step + 1, cnt), void();

    // 情况1：选择当前顶点
    now[step] = step, d[step] = 0;  // 标记为已选择，度数为0
    
    // 更新邻居的度数
    for (int i : g[step])
        if (!now[i])
            d[i]--;
    
    dfs(step + 1, cnt + 1);  // 递归处理下一个顶点

    // 情况2：不选择当前顶点，但选择其所有邻居
    for (int i : g[step])
        if (!now[i])
            cnt++, now[i] = step, tmp[i] = d[i] + 1, d[i] = 0;  // 选择邻居

    // 更新邻居的邻居的度数
    for (int i : g[step])
        if (now[i] == step)
            for (int j : g[i])
                if (!now[j])
                    d[j]--;

    now[step] = 0, dfs(step + 1, cnt);  // 递归处理下一个顶点

    // 恢复状态
    for (int i : g[step])
        if (now[i] == step)
            for (int j : g[i])
                if (!now[j])
                    d[j]++;

    // 恢复邻居的状态
    for (int i : g[step])
        if (now[i] == step)
            now[i] = 0, d[i] = tmp[i];
}

// 解决单个测试用例
inline void solve() {
    scanf("%d%d%d", &n, &m, &k);  // 输入顶点数、边数、目标覆盖数

    // 输入边
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &e[i].first, &e[i].second);

    sort(e + 1, e + 1 + m);  // 排序边以便去重

    // 添加边到图中（去重）
    for (int i = 1; i <= m; i++)
        if (e[i] != e[i - 1])
            add(e[i].first, e[i].second);

    // 初始化答案数组
    for (int i = 1; i <= n; i++)
        ans[i] = 0;

    dfs(1);  // 开始搜索
    m = 0;   // 重用m变量统计覆盖顶点数

    // 统计覆盖顶点数
    for (int i = 1; i <= n; i++)
        m += ans[i], g[i].clear(), d[i] = 0;  // 同时清空图结构

    // 输出结果
    if (m) {
        printf("%d %d\n", k, m);  // 输出覆盖数和顶点数
        for (int i = 1; i <= n; i++)
            if (ans[i])
                printf("%d ", i);  // 输出被选中的顶点
        printf("\n");
    } else {
        printf("-1\n");  // 无解情况
    }
}

// 主函数
int main() {
    cin >> t;  // 输入测试用例数
    while (t--)
        solve();  // 处理每个测试用例
    return 0;
}