问题背景给定 $t$ 个测试用例，每个用例包含一个无向图（$n$ 个顶点、$m$ 条边）和初始目标覆盖数 $k$。要求找到该图的最小顶点覆盖—— 即一个顶点集合，使得图中每条边至少有一个端点属于该集合。最终输出最小覆盖数、覆盖集合的顶点个数及具体顶点；若无解则输出 $-1$。注：输入边可能存在重复，需先去重再处理；顶点编号从 $1$ 开始，所有操作均为常规图论处理逻辑。

核心思路整体采用 DFS 回溯 + 连通分量分类处理 + 剪枝优化 的策略，分四步完成求解：

图的初始化与构建 输入顶点数 $n$、边数 $m$、初始目标覆盖数 $k$，存储所有边到数组 $e$ 中。对边数组排序并去重，避免重复边影响度数计算和邻接关系。通过邻接表 $g$ 存储图结构，同时维护数组 $d$ 记录每个顶点的度数（边数统计）。

DFS 回溯搜索框架 递归参数：$step$（当前处理的顶点编号）、$cnt$（当前已选择的顶点数量）。 剪枝策略：若当前选择数 $cnt > k$，直接返回（超出目标覆盖数，无意义）。 递归终止：当 $step > n$ 时，处理所有顶点，验证并更新最小覆盖集合（见步骤 3）。 二选一决策（仅针对度数 $>2$ 的顶点）：

选择当前顶点：标记 $now[step] = step$，将其度数置为 $0$（已覆盖所有关联边），并减少其未被选择邻居的度数（关联边已覆盖），递归处理下一个顶点。

不选择当前顶点：必须选择其所有邻居（才能覆盖关联边），标记邻居的 $now$ 状态，记录邻居原始度数到 $tmp$ 数组，将邻居度数置为 $0$，并减少邻居的未被选择邻居的度数，递归处理下一个顶点。 状态恢复：递归返回后，恢复邻居的度数（通过 $tmp$ 数组）和 $now$ 选择状态，确保回溯不影响后续搜索。

连通分量分类处理 递归终止后，对图中未标记的顶点按度数分类，处理剩余连通分量：

度数为 $1$ 的连通分量：用 $dfs2$ 遍历整个连通分量（压入栈 $st$）。

若分量大小为偶数：选择所有顶点，覆盖数 $cnt$ 累加分量大小。

若分量大小为奇数：选择第 $2,4,6,...$ 个顶点，覆盖数 $cnt$ 累加 $\lfloor 分量大小 / 2 \rfloor$。

度数为 $2$ 的连通分量：用 $dfs2$ 遍历整个连通分量，选择所有顶点，覆盖数 $cnt$ 累加 $\lceil 分量大小 / 2 \rceil$（即 $(top + 1) >> 1$）。

最优解更新 若当前覆盖数 $cnt < k$：更新最小覆盖数 $k = cnt$，同时更新最终答案数组 $ans$ 为当前临时覆盖集合 $tot$。 若当前覆盖数 $cnt = k$：将临时覆盖集合 $tot$ 合并到 $ans$ 中（$ans[i] |= tot[i]$），确保不遗漏可行解。

直觉理解

顶点覆盖的二选一逻辑：对于度数 $>2$ 的顶点，要么选自己（覆盖所有关联边），要么选所有邻居（覆盖所有关联边），两者必选其一，这是回溯的核心依据。

低度数连通分量的特殊处理：度数为 $1$ 或 $2$ 的连通分量（链或环结构）有固定的最小覆盖策略，无需递归搜索，直接按规则选择即可，大幅提升效率。

剪枝的必要性：通过 $cnt > k$ 提前终止无效路径，减少冗余搜索；度数 $\leq 2$ 的顶点跳过二选一决策，仅处理高度数顶点的递归，降低搜索空间。

状态回溯的意义：$tmp$ 数组记录邻居原始度数，$now$ 数组标记选择状态，回溯时恢复这些信息，确保每个递归分支的独立性。

复杂度分析

图构建与去重：排序边的复杂度为 $O(m \log m)$，邻接表构建与度数统计为 $O(n + m)$。

DFS 回溯：仅度数 $>2$ 的顶点进入二选一递归，设这类顶点数为 $s$，则递归复杂度为 $O(2^s)$。

连通分量处理：$dfs2$ 遍历连通分量的总复杂度为 $O(n + m)$（每个顶点、边仅遍历一次）。

整体复杂度：$O(t \cdot (m \log m + 2^s \cdot (n + m)))$，其中 $s$ 是度数 $>2$ 的顶点数。由于 $s$ 通常远小于 $n$（低度数顶点占比高），剪枝后效率可满足常规输入规模（$n \leq 1005$，$m \leq 3005$）。

#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;
}